The number of multiplicative Sidon sets of integers

DOI10.1016/J.JCTA.2019.02.002zbMATH Open1414.05028arXiv1808.06182OpenAlexW2885443064MaRDI QIDQ2424908

Péter Pál Pach, Hong Liu

Publication date: 25 June 2019

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Abstract: A set $S$ of natural numbers is multiplicative Sidon if the products of all pairs in $S$ are distinct. ErdH{o}s in 1938 studied the maximum size of a multiplicative Sidon subset of $1,ldots,n$, which was later determined up to the lower order term: $pi(n)+Theta(frac{n}^{3/4}(logn{)}^{3/2})$. We show that the number of multiplicative Sidon subsets of $1,ldots,n$ is $T(n)cdot{2}^{Theta(frac{n}^{3/4}(logn{)}^{3/2})}$ for a certain function $T(n)approx{2}^{1.815pi(n)}$ which we specify. This is a rare example in which the order of magnitude of the lower order term in the exponent is determined. It resolves the enumeration problem for multiplicative Sidon sets initiated by Cameron and ErdH{o}s in the 80s. We also investigate its extension for generalised multiplicative Sidon sets. Denote by $S_k$, $kge2$, the number of multiplicative $k$-Sidon subsets of $1,ldots,n$. We show that $$ for some $$ we define explicitly. Our proof is elementary.

Full work available at URL: https://arxiv.org/abs/1808.06182

zbMATH Keywords

cyclescountingunbalanced bipartite graphsmultiplicative Sidon setgraph container lemma

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Exact enumeration problems, generating functions (05A15) Arithmetic combinatorics; higher degree uniformity (11B30)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The number of \(B_3\)-sets of a given cardinality
• Hypergraph containers
• On the number of graphs without 4-cycles
• \(C_ 6\)-free bipartite graphs and product representation of squares
• On the structure of large sum-free sets of integers
• On infinite multiplicative Sidon sets
• Sharp bound on the number of maximal sum-free subsets of integers
• On product representation of powers. I
• Counting primitive subsets and other statistics of the divisor graph of \(\{1,2,\dots,n\}\)
• Generalized multiplicative Sidon sets
• The number of maximal sum-free subsets of integers
• Über ein Problem von K. Zarankiewicz
• Independent Sets in Hypergraphs and Ramsey Properties of Graphs and the Integers
• The Number of Subsets of Integers with Nok-Term Arithmetic Progression
• The number of Bh‐sets of a given cardinality
• THE CAMERON–ERDOS CONJECTURE
• The number of Sidon sets and the maximum size of Sidon sets contained in a sparse random set of integers
• An improved upper bound for the size of the multiplicative 3-Sidon sets
• Independent sets in hypergraphs
• On the Number ofB_h-Sets
• On a problem of K. Zarankiewicz
• The number of maximum primitive sets of integers

Related Items (5)

Integer colorings with no rainbow 3-term arithmetic progression ⋮ Sidon sets for linear forms ⋮ No cubic integer polynomial generates a Sidon sequence ⋮ Recovering affine linearity of functions from their restrictions to affine lines ⋮ The counting version of a problem of Erdős

Recommendations

• Unnamed Item 👍 👎
• On infinite multiplicative Sidon sets 👍 👎
• On strong Sidon sets of integers 👍 👎
• Combinatorial problems in finite fields and Sidon sets 👍 👎
• Generalized multiplicative Sidon sets 👍 👎
• On Multiplicative Sidon Sets 👍 👎
• On the number of generalized Sidon sets 👍 👎
• The number of Sidon sets and the maximum size of Sidon sets contained in a sparse random set of integers 👍 👎
• Additive and multiplicative Sidon sets 👍 👎
• Additive and multiplicative Sidon sets 👍 👎

This page was built for publication: The number of multiplicative Sidon sets of integers