15
$\begingroup$

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

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ Is there a command in GAP to get sl(G) for a group G? $\endgroup$
    – Mare
    Commented Feb 23, 2017 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$
    – მამუკა ჯიბლაძე
    Commented Feb 25, 2017 at 6:27
  • $\begingroup$ @მამუკა ჯიბლაძე Good idea, I mean to add this sequence to OEIS. Thanks. $\endgroup$
    – Taras Banakh
    Commented Feb 26, 2017 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
    Commented Mar 2, 2017 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
    Commented Mar 4, 2017 at 7:35

1 Answer 1

Reset to default
10
$\begingroup$

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.

Improve this answer
$\endgroup$
3