4
$\begingroup$

The Cameron–Erdős conjecture was proved independently by Ben Green (The Cameron-Erdos Conjecture) and Alexander Sapozhenko (The Cameron-Erdős conjecture).

Let $s(n)$ be the number of sum-free subsets of the set of integers $\{1,2,\dotsc,n\}$. They showed that ${ s(n) / 2^{n/2} } \to C_O \text{ or } C_E$, for constants $C_O$ and $C_E$, as $n \to \infty$ through odd or even values respectively.

I would like to know what are the best known bounds for the constants $C_O$ and $C_E$?

My motivation is that I considered the conjecture in the mid-1990s and tried to determine some good lower bounds for the constants on the condition that the limits existed, of course. I have a vague recollection that Cameron and Erdős had some lower bounds in the region of 5 or 6, but I no longer have their relevant papers handy to verify this.

Looking at the sequence A007865 in the OEIS, it would seem that $C_E$ is in the region of 13.4 and that $C_O$ is in the region of 14.4. If one calculates $s(n)/2^{n/2}$ for even $n$, it rises steadily from $n=0$ to $n=36$ then interestingly appears to oscillate about its limit. The sequence for odd $n$, from $n=39$ onwards, possibly does the same. It would be interesting to have some more terms.

Anyway, any information that you have on the actual values of these constants would be greatly appreciated.

$\endgroup$
3
  • $\begingroup$ The OEIS sequence has a link to a table of the first 70 terms, and both Maple and Mathematica code to calculate more values. $\endgroup$ Aug 11, 2010 at 9:16
  • $\begingroup$ I forget whom I learned it from, but it was someone here on MO and so I like to spread it here whenever possible, that the name is not Erdös but Erdős. I have edited accordingly. $\endgroup$
    – LSpice
    Feb 23, 2022 at 14:09
  • 1
    $\begingroup$ Not exactly what you are asking, but certainly related: for finite groups $G$ of even order, the exact value of the constant is known; it is $2^{\nu(G)}-1$, where $\nu(G)$ is the number of even-order components in the canonical decomposition of $G$ into a direct sum of its cyclic subgroups: math.haifa.ac.il/seva/Papers/sfab.dvi $\endgroup$
    – Seva
    Feb 23, 2022 at 21:09

1 Answer 1

4
$\begingroup$

The review of the Sapozhenko paper, The Cameron–Erdős conjecture, Dokl. Akad. Nauk 393 (2003) 749–752, MR 2006a:11027, says $s(n)$ is asymptotic to $(c_0+1)2^{\lceil n/2\rceil}$ when $n$ is even and $(c_1+1)2^{\lceil n/2\rceil}$ when $n$ is odd, with $4.036\le c_0\le4.079$ and $3.086\le c_1\le3.095$.

EDIT: The review of a more recent paper, K. G. Omel'yanov, Estimates for Cameron–Erdős constants, Diskret. Mat. 18 (2006) 55–70, translation in Discrete Math. Appl. 16 (2006) 205–220, MR 2007m:11038, seems to contradict these numbers, giving $5.0709\le c_0\le5.0995$ and $3.8103\le c_1\le3.8336$. I haven't looked at the primary sources, so am unable to say whether the problem lies with me, a reviewer, or an author.

$\endgroup$
1
  • $\begingroup$ Interesting. I wonder why the constants were given in the form you stated in the review of the Sapozhenko paper. (Please could someone email me a copy. My address is [email protected], just substitute my real name and surname. Thanks.) Yes, it looks like there could be disagreement between the values but perhaps in the translation in Discrete Math Appl. they are given in another form, so the two papers aren't talking about exactly the same constants. Please could someone email me a copy of the K G Omel'yanov paper too, as I would like to try and resolve this discrepancy. Thanks. $\endgroup$ Aug 11, 2010 at 12:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.