11
$\begingroup$

$\newcommand{\Z}{\mathbb Z/p\mathbb Z}$ Can one partition a group of prime order as $A\cup(A-A)$ where $A$ is a subset of the group, $A-A$ is the set of all differences $a'-a''$ with $a',a''\in A$, and the union is disjoint?

As stated, the answer is "yes", at least if the order of the group is $p\equiv 2\pmod 3$, in which case one can take $A$ to be an appropriately located interval of an appropriate length: namely, $A=[n,2n-1]$ where $n=(p+1)/3$. One also can dilate $A$ replacing intervals with arithmetic progressions.

Are there any other examples where $A$ and $A-A$ partition the whole group?

Suppose that $A\cup(A-A)$ is a partition of a group of prime order; does it follow that $A$ is an arithmetic progression?

Added two days later. A set found by Peter Mueller in the comments can be generalized to produce infinitely many counterexamples, essentially answering the original question. Specifically, for a prime $p\equiv 5\pmod 8$ let $m:=(p+3)/8$ and define $A:=[-(2m-1),-m]\cup[m,2m-1]$. It is easily verified that then $A-A=[-(m-1),m-1]\cup[2m,p-2m]$, so that $A-A$ is disjoint from $A$, and $A\cup(A-A)$ is the whole group, while $A$ is not an arithmetic progression.

$\endgroup$
3
  • 1
    $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. It would be good if someone wrote an answer based on this discussion. $\endgroup$
    – Ben Webster
    Dec 12, 2022 at 0:22
  • 5
    $\begingroup$ @BenWebster I disagree with this removing of comments, which does not correspond to the usual MO policy and would appreciate if you take this (old) metaMO post in consideration meta.mathoverflow.net/questions/501/cleaning-up-comments $\endgroup$
    – YCor
    Dec 12, 2022 at 1:16
  • 2
    $\begingroup$ @YCor I appreciate the feedback. I had missed the more recent meta post about this (meta.mathoverflow.net/questions/5033/…); given the vote results there, I will be more selective about moving to chat in the future. $\endgroup$
    – Ben Webster
    Dec 14, 2022 at 17:57

2 Answers 2

5
$\begingroup$

This is a previous comment which was moved to chat by Ben Webster: In fact for every prime $p$ if $A=[-(2m-1),-m] \cup [m, 2m-1]$ for $(p+3)/8\le m<(p+3)/6$, then $\mathbb Z/p\mathbb Z$ is a disjoint union of $A$ and $A-A$, and in addition this set $A$ is not an arithmetic progression if and only if $m\ne(p+1)/6$. There are many more examples though. One peculiar sporadic one happens for $p=41$ with $A$ the multiplicative subgroup of order $10$ of $(\mathbb Z/p\mathbb Z)^\star$.

$\endgroup$
5
$\begingroup$

It seemed to me that the commenters know much more about this problem than they write in the comments. For that reason alone I am posting this answer, which is most likely a long comment.

For brevity, we call a symmetric set $A\subset G$ ($G$ is an abelian group) a partitioning set if $G=A\cup(A+A)$ and $A\cap(A+A)=\varnothing$.

The definition from the question (if it were formulated there) is equivalent to this since $A-A$ is symmetric, and then $A$ is also symmetric.

And we also call two partitioning sets $A$ and $B$ of $G$ equivalent if $B=\alpha(A)$ for some $\alpha\in\operatorname{Aut}(G)$.

Everywhere below $G=\mathbb{Z}_p$ for some simple $p$. The conjecture in one of the last comments can be phrased like this: If $A\subset\mathbb{Z}_p$ is a partitioning set, then some equivalent of it lies in $\{-p'd,\ldots,-d,d,\ldots,p'd\}$ where $p'=[p/4]$ and $d$ is a nonzero group element.

For example, the Peter Mueller set for $p=29$ is equivalent to $[4,7]\cup[-7,-4]$ and the set for $p=13$ is equivalent to $[2,3]\cup[-3,-2]$.

Partitioning sets for some other prime: $p=11$, $[2,3]\cup[-3,-2]$; $p=17$ and $p=19$, $[3,5]\cup[-5,-3]$; $p=23$, $[4,7]\cup[-7,-4]$.

In fact, the following statement is true.

Let $p>7$ be a prime. If $p=8m\pm1$ or $p=8m+3$ or $p=8m+5$ and $P=[m+1,2m+1]$, then $A=P\cup-P$ is a partitioning set in $\mathbb{Z}_p$.

And one more remark. For $p=23$ we have a partitioning set $A=[-7,-4]\cup[4,7]$. This set is equivalent to the set $B=[-7,-5,-3,-1,1,3,5,7]$, which is an arithmetic progression.

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