# Is there a nice way to characterize this subset of $Z_n$?

This is a problem I played around with several years ago. I proved a few things, but the proofs were long and messy and not worth reproducing here.

Given a positive integer $n$ and a set $S$ such that $S \subset Z_n$, define a focal point of $n$ and $S$ to be any $a \in Z_n$ such that for each $x \in S$, there exists $y \in S$ such that $x+y \equiv a \mod n$. It is possible to have $x = y$.

Example 1. $n=15$, $S_1=\{1,2,6,7,10,11,12,13\}$. Then $n$ and $S_1$ have the focal point $8$ because $1+7 = 2+6 = 10+13 = 11+12 = 8$. By exhaustion one can show that there are no others.

Example 2: $n=15$, $S_2=\{1,2,6,7,11,12,13\}$. These have no focal points, even though $S_2$ is simply $S_1$ with $10$ removed. In fact, removing any element from $S_1$ results in a set that has no focal points with $n$.

Example 3: $n = 15$, $S_3=\{1,2,6,7,11,12\}$. $S_3$ is obtained by removing both $10$ and $13$ from $S_1$. $S_3$ and $n$ have 3 focal points: $3, 8$, and $13$.

Let $F(n,S)$ be the set of focal points of $n$ and $S$. My questions are these:

1. What can we say about the size of $F(n,S)$? I was able to prove that it must be $0$ or a divisor of $n$, but surely one can say more.
2. Even better, is there a nice way to characterize $F(n,S)$?

My hunch is that the right algebraic structure will make what's going on here crystal clear. Unfortunately, my algebra is quite rusty.

Added: One thing to observe is that in the case of Example 3, $S_3$ splits nicely into residue classes $\bmod 5$: $\{1, 6, 11\}$ and $\{2, 7, 12\}$. If $n_4 = 5$ and $S_4 = \{1,2\}$, then clearly $n_4$ and $S_4$ have one focal point: $3$. Surely it's not a coincidence, then, that $n_3 = 15$ and $S_3=\{1,2,6,7,11,12\}$ have 3 focal points. So perhaps there's a characterization that has to do with when $S$ can be divided into residue classes modulo a divisor of $n$?

-
Mike, please explain what else you're looking for now. It seems to me that the answers by Yuval and Gerry together have correctly described the structure of the problem: The focal points correspond to rotations around axes in the plane of the $n$-gon, the shifts correspond to rotations around the central axis, and together these must form a subgroup of the dihedral group of the $n$-gon, so there are as many shifts as focal points, their number has to be a divisor of $n$, and the possible sets of focal points correspond to the subgroups of the dihedral group. What else would you like to know? – joriki Apr 25 '11 at 16:36
@joriki: That is the kind of thing I was looking for. Algebra is not my strength, and I did not see how to put Gerry Myerson's and Yuval Filmus's answers together to get what you've just said in your comment. Hmmm... so now I have the answer to my question spread across two answers and a comment. Who gets the bounty? Ugh. – Mike Spivey Apr 25 '11 at 16:57
Sorry -- I started writing it as an answer, then felt I was just tying together what Gerry and Yuval had written, and wrote this comment/question instead. I think Gerry should get the bounty, since his answer provided the crucial insight. – joriki Apr 25 '11 at 17:14
@joriki: Thanks. I may give Gerry the bounty, but I'll wait a few days first to see if anybody else has anything to say. – Mike Spivey Apr 25 '11 at 17:21
@joriki: Thank you for your contribution to the answer. I did award Gerry the bounty, but I would like to thank you with rep as well. So I will now go find and upvote some of your answers that I like but haven't upvoted yet. – Mike Spivey May 2 '11 at 3:01

Not an answer, but an attempt to supply an algebraic structure. A regular $n$-sided polygon has $2n$ symmetries - $n$ rotations (counting the "do-nothing" rotation), and $n$ flips. Now take your $n$-sided polygon and color in the vertices corresponding to your set, $S$. I think you'll find the number of focal points is the number of flips that are symmetries of this colored polygon, or, to put it another way, the number of axes of symmetry.

-
Interesting idea. I'll have to think about it some more. – Mike Spivey Apr 21 '11 at 4:26
Thanks, Gerry. Between your answer and Yuval's and joriki's comment, we appear to have the characterization I was looking for. – Mike Spivey May 2 '11 at 2:58

Two simple remarks.

First, $|F(n,S)| \leq |S|$ for obvious reasons.

Second, suppose $a,b \in F(n,S)$. Thus $S$ is closed under $x \mapsto a-x$ and $x \mapsto b-x$, so it is closed under their composition, which is the shift $x \mapsto a-b+x$. Similarly, if $a,b,c \in F(n,S)$ then $a-b+c \in F(n,S)$. So $F(n,S)$ is also closed under shift by $a-b$.

Edit: Here's a nicer way to define $F(n,S)$. Let $T = \{ x : -x \in S \}$. Then $a \in F(n,S)$ iff $S$ is equal to the $a$th cyclic shift of $T$.

Another remark: If $a \in F(n,S)$ is even then $S$ is symmetric with respect to $a/2$. I guess this is also true for odd $a$. In order to see this, it is perhaps better to replace $S$ with $n\mathbb{N} + S$, and then $F(n,S)$ consists of all points of symmetry (doubled).

-
Thanks, Yuval... – Mike Spivey Apr 21 '11 at 4:29
Yuval, thank you for your contribution to the answer. I awarded Gerry the bounty, but I would like to thank you with rep, too. So I will now go find and upvote some of your answers that I like but haven't upvoted yet. – Mike Spivey May 2 '11 at 3:02