A subset $A$ of a group $G$ is defined to be self-linked if $A\cap gA\ne\emptyset$ for all $g\in G$. This happens if and only if $AA^{-1}=G$.

For a finite group $G$ denote by $sl(G)$ the smallest cardinality of a self-linked set in $G$. It is clear that $sl(G)\ge \sqrt{|G|}$. A more accurate lower bound is $sl(G)\ge \frac{1+\sqrt{4|G|-3}}2$. By a classical result of Singer (1938), for any power $q=p^k$ of a prime number $p$, the cyclic group $C_n$ of cardinality $n=1+q+q^2$ contains a self-linked subset of cardinality $1+q$, which implies that $sl(C_n)=1+q=\frac{1+\sqrt{4n-3}}2$. So, for such numbers $n$ the lower bound $\frac{1+\sqrt{4n-3}}2$ is exact. In this paper we prove the upper bound $sl(C_n)\le \sqrt{2n}$ holding for all $n\ne 4$.

Problem 1. Is $sl(C_n)=(1+o(1))\sqrt{n}$?

This problem is equivalent to

Problem 2. Does the limit $\lim_{n\to\infty}{sl(C_n)}/{\sqrt{n}}$ exist?

If the answer to Problems 1,2 are negative, then we can also ask

Problem 3. Evaluate the constant $\lambda:=\limsup_{n\to\infty}{sl(C_n)}/{\sqrt{n}}$.

At the moment it is known that $1\le\lambda\le\sqrt{2}$.

  • 1
    $\begingroup$ Is there a command in GAP to get sl(G) for a group G? $\endgroup$
    – Mare
    Feb 23 '17 at 13:09
  • $\begingroup$ The sequence of the $sl(C_n)$ starts with $1,2,2,3,3,3,3,4,4,4,4,4,4,5,5,5,5,5,5,6,5,6,6,6,6,6,6,6,7,7,6,7,7,7,7,7,7,8,7,8,8,8,8,8,8,8,8,8,8,9,9,9,9,9,...$. It is not on OEIS. $\endgroup$ Feb 25 '17 at 6:27
  • $\begingroup$ @მამუკა ჯიბლაძე Good idea, I mean to add this sequence to OEIS. Thanks. $\endgroup$ Feb 26 '17 at 7:49
  • 1
    $\begingroup$ I vaguely recall that Arieh Lev may have had some results on this problem. Maybe, this paper [ams.org/mathscinet/search/… would be a reasonable starting point. $\endgroup$
    – Seva
    Mar 2 '17 at 14:45
  • 1
    $\begingroup$ (1) Please, use @Seva next time (not just Seva), otherwise I do not get any notification from the system. (2) If you manage to find in the literature any improvements of the basic bounds $(1+o(1))\sqrt n\le {\rm sl}\,(G)\le(1+o(1))\sqrt{2n}$, please, let me know. (3) Check the recent paper by Kohonen (J. Number Theory, 174 (2017)) and the paper of Mrose it refers to: they manage to improve the trivial upper bound for the parallel sum problem $2A=G$, and it is quite possible that their construction can be modified to work for differences. $\endgroup$
    – Seva
    Mar 4 '17 at 7:35

The difference cover problem has been better studied in the context of $\mathbf{Z}$. Redei, Renyi, and others in the 40s asked for the size of the smallest set $A$ such that $A-A$ covers $\{1,2,\dots,N\}$. They proved an upper bound of roughly $\sqrt{8/3} \sqrt{N}$. To prove this they combined Singer's construction of a perfect difference set with the "perfect ruler" $\{0,1,4,6\}$ (which has difference set $\{-6,\dots,6\}$ each with multiplicity one). This was later improved by Leech and Golay to $\sqrt{8/3 - \epsilon}\sqrt{N}$ (for explicit but not very large $\epsilon$). More interestingly, Redei and Renyi proved a nontrivial lower bound of the form $\sqrt{2 + \frac{4}{3\pi}}\sqrt{N}$.

The upper bound can easily be ported to the cyclic problem by taking $N\approx n/2$ and reducing the set $A$ modulo $n$. This proves an upper bound of roughly $\sqrt{4/3}\sqrt{n}$. However, because of the nontrivial lower bound, this proof technique cannot prove $(1+o(1))\sqrt{n}$. Indeed I think it suggests caution.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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