1
$\begingroup$

Assume that the set $A$ does not have simple structures (such as the case that when all elements are odd numbers in $[1,M/2]$ then all sums are even thus there are no solutions, as pointed out by @fedja).

What is the maximum cardinality $n$ of a subset $A$ of $\{1,2,\ldots,M\}$ such that $(A+A) \cap A$ is empty and the set members don't all obey simple diophantine obstructions?

Remark: There is related work for the equation $x+y=2z$ if one allows the set $A$ to be a sumset. In this paper by Croot, Ruzsa and Schoen, according to the comment by @Seva in this mathoverflow question the set $B+B$ has a $k-$term AP as soon as $B\subseteq \{1,\ldots,M\}$ has size $|A|>(3M)^{1-1/(k-1)}.$

Taking the converse of this (letting $k=3$) would seem to say in this restricted case of sumsets and the modified equation, the maximum set size is upperbounded by $(3M)^{1/2}.$

The question remains if any of the techniques in the linked paper, and its references including by Bourgain, Green and others can be applied to my problem. I'd appreciate any pointers in this direction.

$\endgroup$
4
  • $\begingroup$ Is this in reference to something? It seems to be discussing an earlier problem, but without linking the earlier problem, the language is unclear. $\endgroup$
    – user44191
    Dec 12, 2018 at 0:13
  • 1
    $\begingroup$ "Largest cardinality of an $n$-element subset" is $n$, isn't it? You definitely meant something more interesting than that. Also odd integers up to $M/2$ and all integers from $M/2$ to $M$ occupy quite a bit of space already, so if you look for a strong upper bound, it looks hopeless. $\endgroup$
    – fedja
    Dec 12, 2018 at 0:17
  • $\begingroup$ @fedja you're right, fixed typo in title. But it may well be hopeless. $\endgroup$
    – kodlu
    Dec 12, 2018 at 0:23
  • $\begingroup$ I mean, you already have $n\ge \frac 12 M$ with a trivial example. So what does your phrase about $M>n^a$ mean? $\endgroup$
    – fedja
    Dec 12, 2018 at 0:26

1 Answer 1

2
$\begingroup$

As I take it, you want to describe the structure of large sum-free subsets of the interval $[1,M]$, for large values of $M$.

This is in fact a known problem, which has first appeared (in a somewhat implicit form) in a paper by Abbott and Wang some 40 years ago. In 1992 Freiman has shown that a sum-free set $A\subseteq [1,M]$ of size $|A|>\frac5{12}\,M+2$ either consists of odd numbers only, or is in fact contained in the interval $[|A|,M]$. This was further improved in 1999 by Deshouillers, Freiman, Sos and Temkin, who have classified sum-free sets $A\subseteq [1,M]$ of size $|A|\ge\frac25\,M-K$, for any fixed value of $K$ and $M$ sufficiently large; apart from the two above-mentioned scenarios ($A$ consists of odd numbers, or $A\subseteq[|A|,M]$), the set $A$ can be trapped in the union of the residue classes $1$ and $4$ modulo $5$, or in the union of the residue classes $2$ and $3$ modulo $5$, or in the union of two intervals the exact length and location of which depend on $x$.

These results were recently improved by Tuan Tran, who managed to give a description of sum-free subsets of $A\subseteq[1,M]$ of size $|A|>(\frac25-c)M$, with an absolute constant $c>0$. His paper has a very well written introduction, with the references to all the papers I have mentioned and exact statements of the results.

$\endgroup$

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.