7
$\begingroup$

This is a refined version of the question I asked yesterday.

Let $A$ be a finite set of integers with the smallest element $0$ and the largest element $l$. The sumset $C:=3A$ resides in the interval $[0,3l]$, and I write $C_1:=C\cap[0,l)$, $C_2:=C\cap[l,2l]$, and $C_3:=C\cap(2l,3l]$.

Is it true that $|C_2|\ge\min\{|C_1|,|C_3|\}$, for any choice of the set $A$?

A brute force computation shows that there are no counterexamples with $l\le 22$.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

The title and body are asking the question in opposite senses. For the title, the answer is "yes" (it can be thin), and for the body, the answer if "no" (it is not true that it is never thin).

An example is $$ A = \{0,1,2,3,8,11,26,38,56,69,85,89,179,189,197,221,226,243,254,257,264,266,269,270\} $$ where the sumset parts $C_1,C_2,C_3$ have sizes $270, 268, 269$.

Perhaps a word about the construction. The underlying idea was to take two shorter sets $P,Q$ that are as thin (small) as possible, while their sumsets $3P, 3Q$ would cover some interval $[0,b]$ fully. Then make $A = P \cup (l-Q)$ with some conveniently chosen $l$. Hopefully then $3A$ covers the left and right thirds almost fully, while the middle third might have enough holes to make a counterexample. Note the "might" – this is all heuristic, and it is not done until you just try it out.

I took $$P=\{0,1,2,3,8,11,26,38,56,69,85,89\}$$ $$Q=\{0,1,4,6,13,16,27,44,49,73,81,91\}$$ from Challis and Robinson (2010), Some Extremal Postage Stamp Bases, Journal of Integer Sequences 13, Article 10.2.3; Table "h=3" on page 9. Here $P$ and $Q$ are minimal-cardinality additive bases (of order 3) for the interval $[0,186]$, so that part of the construction is done.

Then a brute force search over some possible values of $l$ gave a hit at $l=270$. Indeed, $C_1$ has no "holes" (it covers the integer interval $[0,269]$ fully). $C_2$ has three holes in interval $[270,540]$, and $C_3$ has one hole in interval $[541,810]$.

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ Very cleaver! Any reason why you picked $Q\ne P$? $\endgroup$
    – Yaakov Baruch
    May 31, 2021 at 7:49
  • $\begingroup$ Some more heuristics :) I tried some of the other possibilities from Challis&Robinson, but no success. Also, I was hoping that it works out like this: (1) Because $P,Q$ are constructed to have a thick 3-sumset, we might have thick left and right thirds. (2) Because $P+l-Q$ was not specifically constructed to be thick, it just might be thin. To enchance this hope I thought $P \ne Q$ might be good because they would have, somehow, different characteristics. To be frank I was expecting even more holes in the middle part. $\endgroup$
    – Jukka Kohonen
    May 31, 2021 at 7:56
  • 4
    $\begingroup$ It turns out that $P \ne Q$ was not necessary! Taking $P$ as above, and then just $A = P \cup (260-P)$ gives a smaller counterexample $\{0,1,2,3,8,11,26,38,56,69,85,89,171,175,191,204,222,234,249,252,257,258,259,260\}$ with nice symmetric sizes 260, 259, 260. $\endgroup$
    – Jukka Kohonen
    May 31, 2021 at 8:37

Your Answer

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

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