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$.

  • 0
    A small observation: if the statement is true, then $A+A+A$ also contains all multiples of three.2012-06-27
  • 2
    There are no counterexamples for $n \leq 16$. [Link](http://hpaste.org/70534) to a very naive Haskell program2012-06-27
  • 2
    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\}$.2012-06-27
  • 0
    @sdcvvc Ha! No wonder I had a hard time proving it. (The false result I mean.)2012-06-27
  • 0
    No counterexamples for $n \leq 23$ (if there is no bug in my program).2012-06-28
  • 2
    I've restored the original problem to go side by side with new problem. I think it is less confusing for readers this way.2012-06-28

1 Answers 1

13

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$.

  • 0
    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))2012-06-28
  • 0
    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])2012-06-28
  • 0
    Thanks very much for the counterexample!!2012-06-28
  • 6
    @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.2012-06-28
  • 0
    @CamMcLeman I apologize for modifying the question straight.2012-06-28
  • 0
    @TerryZhou: No need to apologize. There are some subtleties to the system (both technologically and socially) that take some adapt to.2012-06-28
  • 2
    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].2012-06-28
  • 0
    Sorry, both are the same as francis-jamet. 24 and 29, respectively.2012-06-28
  • 0
    @Jacob: Your examples are negated versions of francis's sets.2012-06-29
  • 0
    @sdcvvc Interesting, as it turns out there are only two other counterexamples for n=29. [2, 3, 11, 14, 17, 19, 21] and it's negation along with the other two francis and I have already listed.2012-06-29