Suppose $X\subset \mathbb S^1$ is a finite subset of the group $\mathbb S^1=\mathbb R/\mathbb Z$. We say that $t\in \mathbb S^1$ is a half symmetry of $X$ if $|(X+t)\cap X|>|X|/2$.


**Question.** Can the number of half symmetries of $X$ be larger than $|X|$? If so, is there some reasonable (like $c|X|$) upper bound on the number of half symmetries of $X$?



Number of "half symmetries" of a finite subset of $\mathbb S^1$
**Simple construction.** First, let me answer the question as posed. Let $X$ be any subset of size of $2m$ of $\mathbb{Z}/(3m-1)\mathbb{Z}$. Then every shift of $X$ is a half-symmetry of $X$. Since $\mathbb{Z}$ embeds into $\mathbb{S}^1$, this gives an example with about $(3/2)|X|$ half-symmetries.


**Better construction (slightly informal)**. Let $m$ be an arbitrary integer. Pick each element of $\mathbb{Z}/m\mathbb{Z}$
independent with probability $\tfrac{1}{2}+2\sqrt{\frac{\log m}{m}}$. Then $\mathbb{E}[X]=m/2+\sqrt{m\log m}$. Let $t\neq 0$, and consider $I\_t=|(X+t)\cap X|$. It is distributed approximately as a binomial random variable with mean $(m/2+\sqrt{m\log m})^2/m\approx m/4+\sqrt{m\log m}$. By Chernoff's bound, $P[I\_t\leq m/4]<1/m$. Taking the union bound over all $t\in\mathbb{Z}/m\mathbb{Z}$, we obtain a set $X$ with $(2-o(1))|X|$ half-symmetries.


**Better construction (more formal).** I said *approximately a binomial random variable* because different elements of $(X+t)\cap X$ are not completely independent. However, it is easy to fix: Choose $m$ to be prime, with $|X|$ being chosen by picking elements independent as above. By multiplying everything by $t^{-1}$, we see that the random variables $I\_t$ and $I\_1$ are identically distributed. So, consider $I\_1$. Let $R\_x$ be the characteristic random variable of the event event $x\in X\cap(X+1)$. The variables $R\_0,R\_2,R\_4,\dotsc,R\_{p-3}$ are independent because they depend on independent choices for elements of $X$. Namely, $R\_0$ depends only on whether $0\in X$ and $1\in X$, whereas $R\_2$ depends only on whether $2\in X$ and $3\in X$, etc. For the similar reason, the random variables $R\_1,R\_3,R\_5,\dotsc,R\_{p-2}$ are independent. Let $A=R\_0+R\_2+\dotsb+R\_{p-3}$ and $B=R\_1+R\_3+\dotsb+R\_{p-2}$. So, $I\_t=A+B+R\_{p-1}$ is a sum of two binomial random variables and a little correction. We can bound the deviations of each of these binomial random variables by Chernoff to show that both events "$A\leq m/8$" and "$B\leq m/8$" are unlikely, and hence $I\_1$ is very likely to be greater than $m/4$. Then taking the union bound over different $t\neq 0$ completes the formal proof.


**Simple almost construction.** Let $X$ be the set of quadratic residues in $\mathbb{Z}/p\mathbb{Z}$. Then $X\cap (X+t)$ has size almost $|X|/2$ for every $t$. So, it fails to be a example of a set with $2|X|$ half-symmetries only barely.


