Sumset that covers $\mathbb{Z}/p\mathbb{Z}$.

Let $p$ be a prime. Let $S$ be a set of residues modulo $p$. Define $$S^2 = \{a \cdot b \mid a \in S, b \in S\}.$$

Question: How small can we make $|S|$ such that $\{0, 1, \cdots, p-2, p-1\} \in S^2$ ?

It seems that the optimal bound should be around $\sqrt{2p}$. This can either be seen from a probabilistic argument or by recognizing that if $|S| = k$ then $S^2$ can cover $\dbinom{k}2$ elements. I am able to get a bound of $ \sim 2 \sqrt{p}$ as follows. Let $g$ be a generator of $(\mathbb{Z}/p\mathbb{Z})^{\times}.$ Then we can have the following powers of $g$ in $S:$ $$S = \{ g, g^2, g^3, \cdots, g^{\sqrt{p}}, g^{2 \sqrt{p}}, g^{3 \sqrt{p}}, \cdots, g^{(\sqrt{p}-1) \sqrt{p}} \}.$$

Can we do better ?

Solution 1:

I am sorry for the delay with the answer, I have to do some urgent stuff these weeks. So now I quickly share my present data with you, but I hope to look at our findings later.

So, Taras Bahakh also thinks that this question should be classical and well-investigated, but, surprisingly, both his and mine google searches have yielded only a few references.

By $\Bbb Z_n$ I denote the cyclic group $\Bbb Z/n\Bbb Z$.

In [DG] Grekos announced that for certain $h$ they constructed a set $S\subset \Bbb Z_n=S^h$ of much smaller size than the known upper bound $hn^{1/h}$ due to Hans Rohr-bach [R]. Unfortunately, Taras Banakh failed to find the respective article.

Paper [FJ] by Fitch and Jamison reports on an exhaustive computer search yielding a census of all minimum sum covers in cyclic groups up to order $54$. Following this paper by $\operatorname{msc}(n)$ we denote the minimal size of a smallest sum cover of the group $\Bbb Z_n$. Just after the definition they remarked “Just by counting, it is easy to derive a fairly good lower bound, which unfortunately, is the only generally valid lower bound known”. Namely, in Theorem 1.1 is stated that $\operatorname{msc}(n)\ge \frac{1+\sqrt{1+8n}}2$ for each $n$. In the next Theorem 1.2, tweaking your idea to a base $b=\lceil \sqrt{n} \rceil$ representation of the integers, they obtain an upper bound $\operatorname{msc}(n)\le\lceil 2\sqrt{n}\rceil$. Fitch and Jamison remarked “It is immediately obvious that this argument can be tweaked to yield a better bound. Unfortunately, the improvement is only slight and the verification becomes much more tedious. We have therefore elected to give only the simple, transparent case here to illustrate the general method. The improved bounds will be investigated more thoroughly in a forthcoming paper [EJ]... The construction does illustrate, however, a key theme of this paper and that is the role played by arithmetic progressions in sum covers. Indeed, the two sets $P$ and $Q$ above are both arithmetic progressions” ... “the best known general constructions are close to the base $b$ construction of Theorem 1.2”.

Taras Bahakh also told me that our colleague Volodymyr Gavrylkiv also calculated minimal sizes of sum-bases for small cyclic groups, but he already forgot Volodymyr’s results.

For a general case, Taras Banakh told me that Kozma and Lev proved that each finite group $G$ has sum-basis of size at most $\frac{4}{\sqrt{3}}\sqrt{|G|}$.

I also have found a paper [Haa], but have not studied it yet. I guess that a result of Mrose [Mro] for $\Bbb Z$ counterpart of the problem should imply that $\operatorname{lim sup}_{n\to\infty} \frac{\operatorname{msc}(n)}{\sqrt{n} } \le\frac{7}{4}$, see [Hor]. I looked for papers again, and it seems that in this direction was mainly investigated the $\Bbb Z$ counterpart of the problem, for which is devoted a lot of papers, in which the lower bound was more and more improved by complicated techniques, see, for instance [Mos], [GN], [Hor], [Yu] I also found that another my colleague, Oleg Pikhurko dealt with a related stuff in his paper [Pih]. In particular, he noted that Mrose [Mro] constructed a set $S\subset [0, 10t^2+8t]$ of size $7t + 3$ such that $S + S\supset [0, 14t^2 + 10t − 1]$. In fact, $S$ is the union of five disjoint arithmetic progressions, see the description at p. 6 of Pikhurko’s paper.

References

[DG] Georges Grekos, Jean-Marc Deshouillers An additive problem in cyclic groups.

[EJ] Clark, Edwin and Robert E. Jamison Generating all slopes in $\operatorname{AG}(2;q)$ with a minimum number of points, in preparation. (Google didn’t find this paper)

[FJ] Mark A. Fitch and Robert E. Jamison Minimum sum covers of small cyclic groups, Congr. Numer. 147 (2000), 65-81.

[GN] C. Sinan Güntürk, Melvyn B. Nathanson A new upper bound for finite additive bases, Acta Arithmetica 124 (2006), 235-255.

[Haa] Harri Haanpää Minimum Sum and Difference Covers of Abelian Groups Journal of Integer Sequences, 7 (2004), Article 04.2.6.

[Hor] G. Horváth An improvement of an estimate for finite additive bases, Acta Arithmetica 130 (2007), 369-380.

[Mos] L. Moser On the representation of $1,2,\dots, n$ by sums, Acta Arithmetica 6 (1960), 11-13.

[Mro] A. Mrose, Untere Schranken für die Reichweiten von Extremalbasen fester Ordnung, Abh. Math. Sem. Univ. Hamburg 48 (1979), 118–124. (I didn’t looked for this paper because I cannot read in German)

[Pih] Oleg Pikhurko Dense Edge-Magic Graphs and Thin Additive Bases.

[R] Hans Rohr-bach Ein Beitrag zur additiven Zahlentheorie. Math. Z. 42, 1-30 (1936).

[Yu] Gang Yu Upper bounds for finite additive $2$-bases, Proc. Amer. Math. Soc. 137 (2009), 11-18.

Solution 2:

This is possibly too long for a comment, but I think it is useful in looking at this problem. Let $G$ be a group. For $H,K\subseteq G$ define $$HK=\{hk\;|\; h\in H,\; k\in K\}$$ Then a good generalization of your question is

What is the smallest $S\subseteq G$ such that $S^2=G$?

Notice that in your case $G=(\mathbb{Z}/p\mathbb{Z})^{\times}$, and really what you wanted was $S^2=\mathbb{Z}/p\mathbb{Z}$, not $S^2=G$. However as noted by the comments if $S^2=G$, then $(S\cup \{0\})^2=\mathbb{Z}/p\mathbb{Z}$, and if $S^2=\mathbb{Z}/p\mathbb{Z}$ then $0\in S$ and $(S\setminus \{0\})^2=G$. Thus the answer to your question is simply $+1$ to the more natural general question proposed with $G=(\mathbb{Z}/p\mathbb{Z})^{\times}$, because we just add $0$ to the minimal set.

Define $$\phi(G)=\min\{|S|\; |\; S\subseteq G, \; S^2=G\}$$ The first observation is quite obvious

If $G_1\cong G_2$, then $\phi(G_1)=\phi(G_2)$.

So as noted by the comments since $(\mathbb{Z}/p\mathbb{Z})^{\times}\cong Z_{p-1}$ (where $Z_n$ is the cyclic group of order $n$), we can consider this problem in the slightly easier to understand additive group $\mathbb{Z}/p\mathbb{Z}$. And to understand the problem at hand we really only need to understand $\phi$ on cyclic groups. We then have two useful properties.

Some of the papers in the comments talk about difference basis. If $\Delta[G]$ is the smallest cardinality of a difference basis, then we have $\phi(G)\le 2\Delta[G]$. Using the results of those papers we then have $$\phi(G)\le \frac{8}{\sqrt{3}}\sqrt{|G|}\qquad\text{and}\qquad \phi(Z_n)\le 3\sqrt{n}$$ So for your question we have the bound $3\sqrt{p-1}$. However we can slightly improve this bound in specific cases. Note that

If $H\le G$, then $\phi(G)\le |H|+|G|/|H|-1$.

This is because the cosets of $H$ partition $G$, so pick out the set $R$ of representatives of the cosets, with $|R|=|G:H|=|G|/|H|$. Then $RH=G$, and so $(R\cup H)^2\supseteq RH=G$. Thus $\phi(G)\le |R\cup H|=|H|+|G|/|H|-1$. This gives us the following bound which is an improvement of the aforementioned ones in special cases

Suppose $G$ is nilpotent (or just CLT). Write $|G|=n^2m$ where $m$ is square-free, then $\phi(G)\le n(m+1)$.

Since $G$ is CLT, there exists a subgroup of order $n\mid |G|$. Thus by the earlier property $\phi(G)\le n+nm=n(m+1)$.
For your question this is an improvement only when $p=n^2+1$, in which case we get the bound $2\sqrt{p-1}$. I think the best way to do better than this is look at the papers on difference bases and emulate them for your question.

Extra Stuff

Property 1. $\phi(H\times K)\le \phi(H)\phi(K)$

The proof of course being if $S_1^2=H$ and $S_2^2=K$, then $(S_1\times S_2)^2=H\times K$. There's a chance that this is an equality, which I haven't been able to assess yet. And finally we notice that

Property 2. Let $N\le Z(G)$, then $\phi(G)\le \phi(G/N)\phi(N)$.

Let $R$ be a fixed set of representatives of the cosets on $N$ with the group operation defined by $r_1,r_2\in R$, then $r_1r_2=r_3$ where $r_3$ is such that $r_1r_2N=r_3N$. Of course, $R\cong G/N$. Now let $R_0$ be such that $R_0^2=R$ and $|R_0|=\phi(R)=\phi(G/N)$, and let $S_0$ be such that $S_0^2=N$ and $|S_0|=\phi(N)$. Since $S_0\subseteq N\subseteq Z(G)$, we have $R_0S_0=S_0R_0$, and since the cosets of $N$ partition $G$, it follows that $$(R_0S_0)^2=R_0^2S_0^2=RN=\bigcup_{r\in R}rN=G$$ Thus $\phi(G)\le |R_0S_0|\le |R_0|\cdot |S_0|\le \phi(G/N)\phi(N)$.
This gives us the following property.

Property 3. Suppose $G$ is nilpotent, then $$\phi(G)\le \prod_{p^{\alpha}\, \mid\mid \, |G|}\phi(Z_p)^{\alpha}$$

First it follows from Property 2 that if $|P|=p^{\alpha}$ then $\phi(P)\le \phi(Z_p)^{\alpha}$. This is because $p$-groups have a normal subgroup of order $p$ contained in their center, allowing us to inductively apply Property 2. Then since $G$ is nilpotent it is the direct product of its Sylow subgroups allowing us to apply this fact and Property 1 to get the result.