21
$\begingroup$

Original Problem: Counterexample given below by user francis-jamet.

Let $A\subset \mathbb Z_n$ for some $n\in \mathbb{N}$.

If $A-A=\mathbb Z_n$, then $0\in A+A+A$


New Problem: Is the following statement true? If not, please give a counterexample.

If $A-A=\mathbb Z_n$ and $0\not\in A+A$, then $0\in A+A+A$.

$\endgroup$
  • $\begingroup$ A small observation: if the statement is true, then $A+A+A$ also contains all multiples of three. $\endgroup$ – Colin McQuillan Jun 27 '12 at 16:26
  • 2
    $\begingroup$ There are no counterexamples for $n \leq 16$. Link to a very naive Haskell program $\endgroup$ – sdcvvc Jun 27 '12 at 18:18
  • 2
    $\begingroup$ All tests pass $A - A = {\mathbb Z}_n \implies A + A + A = {\mathbb Z}_n$. The stronger conclusion $A + A = \mathbb {\mathbb Z}_n$ is false: $n=6$ and $A=\{1,2,4\}$. $\endgroup$ – sdcvvc Jun 27 '12 at 19:10
  • $\begingroup$ @sdcvvc Ha! No wonder I had a hard time proving it. (The false result I mean.) $\endgroup$ – user940 Jun 27 '12 at 19:27
  • 2
    $\begingroup$ I've restored the original problem to go side by side with new problem. I think it is less confusing for readers this way. $\endgroup$ – user940 Jun 28 '12 at 14:08
13
$\begingroup$

For the original problem, there is a counterexample for $n=24$ and $A=\{3,9,11,15,20,21,23\}$.

There are no counterexamples for $n \leq 23$.

For the new problem, there is a counterexample:

$n=29$ and $A=\{4,5,6,9,13,22,28\}$.

There are no counterexamples for $n \leq 28$.

$\endgroup$
  • $\begingroup$ A test in Python (it gives "True"): a=[3,9,11,15,20,21,23]; set([(x-y+24) % 24 for x in a for y in a])==set(range(24)) $\endgroup$ – Colin McQuillan Jun 28 '12 at 9:08
  • $\begingroup$ Oh, and the following expression evaluates to False: 0 in set([(x+y+z) % 24 for x in a for y in a for z in a]) $\endgroup$ – Colin McQuillan Jun 28 '12 at 9:09
  • $\begingroup$ Thanks very much for the counterexample!! $\endgroup$ – Terry Zhou Jun 28 '12 at 13:34
  • 6
    $\begingroup$ @TerryZhou: So as not to undermine francis-jamet's efforts in solving your original problem, I think it would make more sense to start a new question and include a link to this one. $\endgroup$ – Cam McLeman Jun 28 '12 at 14:29
  • 2
    $\begingroup$ I just finished writing a program to search for counterexamples to both problems as francis updated this. So I'll just leave my results as a comment. I found another counterexample to the original problem [1,3,4,9,13,15,21]. And to the second problem I found [1,7,16,20,23,24,25]. $\endgroup$ – JSchlather Jun 28 '12 at 18:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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