Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
The condition 2a=b+c mod n reminds me of Fox n-coloring on a knot. For example, see page 3 of arxiv.org/abs/1301.5378 –  Aeryk Sep 25 '13 at 16:30
add comment

3 Answers

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.

share|improve this answer
add comment

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

share|improve this answer
    
Dear Robert: Is Cplex able to find all the feasible solutions? –  Binzhou Xia Sep 26 '13 at 3:16
    
@BinzhouXia: Apparently it is possible using IncumbentCallback: basically you reject each solution Cplex finds and tell it to continue searching. I haven't used this myself. –  Robert Israel Sep 29 '13 at 4:16
add comment

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

share|improve this answer
    
Dear Lucia: Thank you so much for the wonderful references! I also believe that a good start may be when $l$ is prime. But it appears that $k$ can be values other than $1$ and $l$. For example $S=\{0,1,2,3,6,11\}$ when $l=7$. –  Binzhou Xia Sep 28 '13 at 3:56
    
You're right. So the structure theorem I referred to gives here that the odd numbers 1, 3, 11 are three numbers out of the progression 11, 13, 1, 3; and the even numbers 0, 2, 6 are three out of the progression 0, 2, 4, 6. So a result of that type is perhaps the best you could get. –  Lucia Sep 28 '13 at 4:01
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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