The generalized Sidon set counting conjecture

An α\alpha-generalized Sidon set in [n]={1,,n}[n]=\{1,\ldots,n\} is a set containing at most α\alpha Sidon 4-tuples. Let Nn(α)N_n(\alpha) denote the number of α\alpha-generalized Sidon sets in [n][n]. Generalized Sidon set counting conjecture. For

α=Θ(nlog4n),\alpha=\Theta\left(\frac{n}{\log^4 n}\right),

one has

Nn(α)=2Θ(n).N_n(\alpha)=2^{\Theta(\sqrt n)}.

The paper proves matching-order behavior for α=O(n/log5n)\alpha=O(n/\log^5 n) and gives upper bounds at the scale n/log4nn/\log^4 n, while a probabilistic lower-bound argument shows that values substantially larger than this scale cannot have the same growth order. The claim that the exponent 44 is best possible remains open.

Sources & referencesView supporting material

Primary source

József Balogh and Lina Li, “On the number of generalized Sidon sets”, arXiv:1803.00659 (2018).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.