The number of multiplicative Sidon sets of integers

DOI10.1016/J.JCTA.2019.02.002MaRDI QIDQ2424908zbMATH OpenOpenAlexFDO

Authors Hong Liu, Péter Pál Pach

Publication date 25 June 2019

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

Full work available at URL https://arxiv.org/abs/1808.06182, http://real.mtak.hu/99393/1/The_number_JCTA.pdf

zbMATH Keywords

countingcyclesgraph container lemmamultiplicative Sidon setunbalanced bipartite graphs

Mathematics Subject Classification ID

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

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.

Recommendations

• On multiplicative Sidon sets
• On the number of generalized Sidon sets
• On strong Sidon sets of integers
• Generalized multiplicative Sidon sets
• On infinite multiplicative Sidon sets
• Additive and multiplicative Sidon sets
• Additive and multiplicative Sidon sets
• The number of Sidon sets and the maximum size of Sidon sets contained in a sparse random set of integers
• Combinatorial problems in finite fields and Sidon sets
• scientific article; zbMATH DE number 4137896

Cites work

• \(C_ 6\)-free bipartite graphs and product representation of squares
• An improved upper bound for the size of the multiplicative 3-Sidon sets
• Counting primitive subsets and other statistics of the divisor graph of \(\{1,2,\dots,n\}\)
• Generalized multiplicative Sidon sets
• scientific article; zbMATH DE number 4137896 (Why is no real title available?)
• scientific article; zbMATH DE number 3232670 (Why is no real title available?)
• scientific article; zbMATH DE number 3330856 (Why is no real title available?)
• Hypergraph containers
• Independent sets in hypergraphs
• Independent sets in hypergraphs and Ramsey properties of graphs and the integers
• On a problem of K. Zarankiewicz
• On infinite multiplicative Sidon sets
• On product representation of powers. I
• On the number of B_h-sets
• On the number of graphs without 4-cycles
• On the structure of large sum-free sets of integers
• Sharp bound on the number of maximal sum-free subsets of integers
• THE CAMERON–ERDOS CONJECTURE
• The number of B₃-sets of a given cardinality
• The number of Bh‐sets of a given cardinality
• The number of maximal sum-free subsets of integers
• The number of maximum primitive sets of integers
• The number of Sidon sets and the maximum size of Sidon sets contained in a sparse random set of integers
• The number of subsets of integers with no k-term arithmetic progression
• Über ein Problem von K. Zarankiewicz

Cited in

(11)

• On infinite multiplicative Sidon sets
• Integer colorings with no rainbow 3-term arithmetic progression
• The counting version of a problem of Erdős
• Generalized multiplicative Sidon sets
• Sidon sets for linear forms
• On multiplicative Sidon sets
• An improved upper bound for the size of the multiplicative 3-Sidon sets
• Additive and multiplicative Sidon sets
• Additive and multiplicative Sidon sets
• No cubic integer polynomial generates a Sidon sequence
• Recovering affine linearity of functions from their restrictions to affine lines

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2424908)