Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The Cameron-Erdös conjecture was proved independently by Ben Green and Alexander Sapozhenko.

Let s(n) be the number of sum-free subsets of the set of integers {1,2,...,n}. They showed that ${ s(n) / 2^{n/2} } \to C_O \hbox{ 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 at $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.

share|improve this question
    
The OEIS sequence has a link to a table of the first 70 terms, and both Maple and Mathematica code to calculate more values. –  Hugo van der Sanden Aug 11 '10 at 9:16
    
Many thanks Hugo. –  Derek Jennings Aug 11 '10 at 12:31

1 Answer 1

The review of the Sapozhenko paper, The Cameron-Erdos 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-Erdos 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.

share|improve this answer
    
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 namesurname@ntlworld.com, 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. –  Derek Jennings Aug 11 '10 at 12:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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