Choosing elements from an abelian group $\mathbb{Z}_n$ that make the enumeration of partitions incomplete.

Question

Take an abelian group $(\mathbb{Z}_n,+)$ and enumerate all partitions of two elements (i.e. $x=x_1+x_2$) of each element $\{0,1,...,n-1\}=\mathbb{Z}_n$. Take, for example, abelian groups $\mathbb{Z}_9$ and $\mathbb{Z}_{10}$. Now, the enumerations of the partitions of these groups would be the following (note that $x=x_1+x_2$ where $x_1=x_2$ is not allowed, i.e. $x_1$ and $x_2$ may not be equal!):

$\mathbb{Z}_9:$

$0=8+1,7+2,6+3,5+4$

$1=8+2,7+3,6+4,0+1$

$2=8+3,7+4,6+5,0+2$

$3=8+4,7+5,0+3,1+2$

$4=8+5,7+6,0+4,1+3$

$5=8+6,0+5,1+4,2+3$

$6=8+7,0+6,1+5,2+4$

$7=0+7,1+6,2+5,3+4$

$8=0+8,1+7,2+6,3+5$

$\mathbb{Z}_{10}:$

$0=9+1,8+2,7+3,6+4$

$1=9+2,8+3,7+4,6+5,0+1$

$2=9+3,8+4,7+5,0+2$

$3=9+4,8+5,7+6,0+3,1+2$

$4=9+5,8+6,0+4,1+3$

$5=9+6,8+7,0+5,1+4,2+3$

$6=9+7,0+6,1+5,2+4$

$7=9+8,0+7,1+6,2+5,3+4$

$8=0+8,1+7,2+6,3+5$

$9=0+9,1+8,2+7,3+6,4+5$

Now, my question is the following: how many ways can we choose the total of $\lfloor \frac{n-1}{2}\rfloor$ distinct elements from $\mathbb{Z}_n$ such that when these elements are deleted, there exists at least one remaining element in $\mathbb{Z}_n$ that may not be expressed as a partition $x=x_1+x_2$ anymore. For instance, if we look at $\mathbb{Z}_9$ then $\lfloor \frac{9-1}{2} \rfloor=4$ and if we delete $\{8,2,3,5\}$ from $\mathbb{Z}_9$ then we cannot express $0$ as a partition $0=x_1+x_2$ where $x_1,x_2\in \mathbb{Z}_9 \setminus \{8,2,3,5\}$.

I noticed that no $\lfloor \frac{n-1}{2} \rfloor$ consecutive elements may be deleted from $\mathbb{Z}_n$ so there must be at least $n$ different ways to do this. However, there have to be more than $n$ due to, for instance, my previous example of $\mathbb{Z}_9\setminus \{8,2,3,5\}$.

Answer 1

The answer is $p\cdot 2^{(p-1)/2}-\frac{p(p-1)}{2}$ for prime $p > 2$.

You want the number of $A \subseteq \mathbb{Z}_p$ of size $|A| = \frac{p+1}{2}$ so that $|A\hat{+}A| \le p-1$, where $A\hat{+}A := \{a+a' : a,a' \in A, a \not = a'\}$.

Take $A \subseteq \mathbb{Z}_p, |A| = \frac{p+1}{2}$. It's known that $|A\hat{+}A| \ge \min(p,2|A|-3) \ge p-2$ (see, e.g., here).

We first claim that for any distinct $a,b \in \mathbb{Z}_p$, there's exactly one $A \subseteq \mathbb{Z}_p, |A| = \frac{p+1}{2}$ with $|A\hat{+}A| = \mathbb{Z}_p\setminus\{a,b\}$. By translation and scaling, it suffices to show this for $a=0,b=1$. Since, by Cauchy-Davenport $A+A = \mathbb{Z}_p$, we must have $2^{-1}0,2^{-1}1 \in A$. I.e., we must have $0,\frac{p+1}{2} \in A$. Since $1 \not \in A$, we must have $p-1 \in A$. You can keep playing this game.

And for any $a$, there are $2^{(p-1)/2}$ subsets $A \subseteq \mathbb{Z}_p, |A| = \frac{p+1}{2}$ with $a \not \in A\hat{+}A$. The number of them with $A\hat{+}A = \mathbb{Z}_p\setminus\{a\}$ is thus $2^{(p-1)/2}-(p-1)$.

So the answer is $p(2^{(p-1)/2}-(p-1))+{p \choose 2} = p\cdot 2^{(p-1)/2}-\frac{p(p-1)}{2}$.

---

For odd $n$, the answer is $$n\cdot\left(2^{(n-1)/2}-\sum_{j=1}^{n-1} \gcd(j,n)\right)+\sum_{0 \le x < y \le n-1} \gcd(x-y,n).$$ To see this, one first shows $|C\hat{+}C| \ge n-2$ for any $C \subseteq \mathbb{Z}_n, |C| = \frac{n+1}{2}$ and that the number of $C$ with $C\hat{+}C = \mathbb{Z}_n\setminus\{x,y\}$ is $\gcd(x-y,n)$ (by translation, it suffices to prove this for $y=0$).

All such $C$ are a union of cosets of a subgroup and part of one coset.