A question on residues mod an even integer

Question

I posted the question here, but it seems to be more difficult than I expected. So I think it may be suited for MO. (Another reason is that the answer may hopefully give solution to the question on this site.)

Let $k$ and $l$ be integers greater than $4$. My question is to determine the set $S$ of $k$ elements in $\mathbb{Z}/2l\mathbb{Z}$ satisfying the following three conditions:

(1) if $a\in S$, then $a+l\not\in S$;

(2) for any $a\in S$, there exist $b\neq c\in S$ such that $2a=b+c$;

(3) for any $b\neq c\in S$ such that $b+c$ is even (this makes sense since $2l$ is even), there exists $a\in S$ such that $2a=b+c$.

An observation is that whenever $S$ is a set satisfying the above conditions, $S+m$ is also such a set for all $m\in\mathbb{Z}/2l\mathbb{Z}$.

It is easy to verify that when $k$ is odd and $l=kn$, the set $\{t,t+2n,t+4n,\dots,t+2(k-1)n\}$ satisfies the three conditions for all $t\in\mathbb{Z}/2l\mathbb{Z}$. But I'm not aware of any other examples yet. (If these are the only satisfactory sets, then I am able to give an affirmative answer to this question.)

Answer 1

The examples listed in the question are not the only ones -- for instance, if $k=l=5$ then you can take $S=\{0,1,2,4,8\}$.

I note that there are a few ways of constructing more solutions from a given solution. For instance, if $S$ is a solution in $\mathbb{Z}/2l\mathbb{Z}$ then $t+nS$ is a solution in $\mathbb{Z}/2ln\mathbb{Z}$ for any $t$ and $n$ such that either $n$ is odd or all elements of $S$ are even. Thus, the solutions listed in the question all come from the solution $\{0,2,4,6,...,2k−2\}$ with $k=l$.

Next, if $S_1$ and $S_2$ are two solutions in $\mathbb{Z}/2l\mathbb{Z}$ with $l$ even such that all elements of $S_1$ are even and all elements of $S_2$ are odd, then $S_1\cup S_2$ is a solution. Thus, for example, from the solution $\{0,2,4\}$ with $l=3$ we can build the solution $\{0,1,4,5,8,9\}$ with $l=6$; and from $\{0,2,4\}$ with $l=3$ and $\{0,2,4,6,8\}$ with $l=5$ we can build the solution $\{1,21,41\}\cup\{0,12,24,36,48\}=\{0,1,12,21,24,36,41,48\}$ with $l=30$.

There are probably further ways to build new solutions from old ones, and it seems that one should take account of these in order to have any hope of describing all solutions.

Answer 2

For any particular $k$ and $l$, you can express your constraints in terms of binary integer programming and search for solutions using software such as Cplex. Thus let $x_i = 1$ if $i \in S$, $0$ otherwise, and $y_{ij} = 1$ if $\{i,j\} \subseteq S$, $0$ otherwise. You have constraints

$$\eqalign{\sum_i x_i &= k \cr y_{ij} &\ge x_i + x_j - 1\cr y_{ij} &\le x_i \cr y_{ij} &\le x_j \cr x_a + x_{a+l} &\le 1 \ \text{for}\ a < l\cr \sum_{b} y_{b,2a-b} &\ge x_a\cr x_b + x_c &\le 1 + x_{(b+c)/2} + x_{(b+c)/2\pm l}\ \text{for}\ b + c\ \text{even}\cr }$$

Answer 3

I think there is some structure to your problem, but I haven't fully thought this through. For example, if $\ell$ is prime then I think $k$ must be $1$ or $\ell$. Here are some thoughts on this case. Consider the odd elements $S_{o}$ in $S$ and the even elements $S_{e}$ in $S$. Your conditions impose the restrictions that the sumsets $S_o+S_o$ and $S_e+S_e$ are both at most as big as $S$ in size. If one views these sets just in ${\Bbb Z}/\ell {\Bbb Z}$ (relations are preserved in just viewing the congruences $\pmod \ell$) then this is very close to the extremal case of the Cauchy-Davenport theorem in set addition (since one of $S_o$ or $S_e$ must contain at least half the elements in $S$). In this situation the extremal cases are well understood -- this is known as Vosper's theorem and generalizations, and you would then be able to get the structure of $S_o$ and $S_e$. Essentially they look like progressions with maybe one term omitted. (Note that Zieve's examples look like this.) So you should be able to push this through to obtain a theorem at least for $\ell$ prime. For composite $\ell$ things are more complicated since there are more subgroups, and I don't think precise extensions of Vosper's theorem are known. There is an extensive literature on such inverse problems in additive number theory, and recent work by Serra, Zemor, Hamidoune, Rodseth and many others on this topic. Let me give a pointer to http://arxiv.org/pdf/math/0507561.pdf where you will find other references; also Serra's homepage will contain other papers.

Update: As the OP pointed out my guess that when $\ell$ is prime $k$ must be $1$ or $\ell$ is not correct. What does follow from the inverse theorems referred above I think is that when $\ell$ is prime and $k<\ell$ then $S$ decomposes as the union of $S_o$ and $S_e$ and that each of these sets forms an arithmetic progression missing possibly one term.

More precise version: Here's a more precise version of my comments above. I will assume below that $\ell$ is an odd prime. First we reformulate the problem. Let $S$ be a subset of cardinality $k$ in ${\Bbb Z}/2\ell {\Bbb Z}$ such that no two elements in $S$ are congruent $\pmod \ell$. Let $S_o$ and $S_e$ denote the odd and even elements in $S$. Denote by $2\times S$ the set $\{ 2s: s\in S\}$, so that $2\times S$ also has cardinality $k$. The problem asks for the structure of $S$ given that $(S_o+S_o)\cup (S_e+S_e) = 2\times S$.

If $k =\ell$ there are many such sets and there is no structure. To see this choose a random set of $(\ell+1)/2$ residue classes $\pmod \ell$ and lift these to a set $S_o$ of odd residue classes $\pmod {2\ell}$. Take the complementary set of $(\ell-1)/2$ residue classes $\pmod \ell$ and lift these to the set $S_e$ of even residue classes $\pmod {2\ell}$. With high probability $S_o+S_o =S_e+S_e = \{0, 2, 4, \ldots, 2\ell -2\}$.

If $k=\ell -1$ there is a similar construction. From every pair $i$, $\ell-i$ ($1\le i\le (\ell-1)/2$) choose a random number, and lift these $(\ell-1)/2$ numbers to a set $S_o$. Take the complementary choice and lift that to a set $S_e$. Then with high probability $S_o+S_o = S_e+S_e =\{2,4,6,\ldots, 2\ell -2\}$.

If $k$ is not too close to $\ell$ then one gets structure. This follows from the Hamidoune-Rodseth version of Vosper's theorem that I mentioned above. Precisely suppose that $8\le k\le \ell -4$. Suppose that $S_o$ contains at least $k/2$ elements (similar argument if $S_e$ is the bigger set). From the Cauchy-Davenport theorem one gets that in fact $S_o$ must be of size $\lceil k/2\rceil$ (and so $S_e$ contains $\lfloor k/2\rfloor$ elements). Then from the Hamidoune-Rodseth theorem we find that $S_o$ must be an arithmetic progression missing possibly one term. If $k$ is even, the same conclusion applies to $S_e$. If $k$ is odd (so that $S_o$ has $(k+1)/2$ elements and $S_e$ has $(k-1)/2$ elements) then one needs the stronger result of Serra, Zemor and Hamidoune, and here $S_e$ can omit two elements from an arithmetic progression (if $\ell$ is at least $53$).