Counting minimum elements needed such that their sum covers the whole finite space. In $\mathbb{F}_p$, how to find a subset with smallest cardinality such that the sum between its pairs cover $\mathbb{F}_p\setminus\{0\}$.
So for a subset with cardinality $n$ there are ${n\choose 2}$ pairs and correspondingly ${n\choose 2}$ sums. I want $n$ to be smallest such that those ${n\choose 2}$ sums cover $\mathbb{F}_p\setminus\{0\}$.
For example in $\mathbb{F}_7$, let $A=\{0,1,2,4\}$,
The sums between its pairs covers $\mathbb{F}_7\setminus\{0\}$ since
\begin{align*} 
0+1=1,0+2=2,1+2=3,0+4=4,1+4=5,2+4=6\;.
\end{align*}
I want to know if over large $p$ similar set can be easily constructed and what would be the size of that set (I expect it to be close to $\sqrt{2p}$). Any similar literature is also appreciated.
 A: You can solve the problem via integer linear programming as follows.  For $i\in \{0,\dots,n-1\}$, let binary decision variable $x_i$ indicate whether $i$ is selected.  For $0 \le i < j \le n-1$, let binary decision variable $y_{i,j}$ represent the product $x_i x_j$.  The problem is to minimize $\sum_i x_i$ subject to
\begin{align}
\sum_{\substack{0 \le i < j \le n-1:\\ i + j = k}} y_{i,j} &\ge 1 &&\text{for $k \in \{1,\dots,n-1\}$} \tag1 \\
y_{i,j} &\le x_i &&\text{for $0 \le i < j \le n-1$} \tag2 \\
y_{i,j} &\le x_j &&\text{for $0 \le i < j \le n-1$} \tag3
\end{align}
Constraint $(1)$ forces each sum $k$ to be covered.
Constraints $(2)$ and $(3)$ enforce the logical implication $y_{i,j} \implies (x_i \land x_j)$.
The values for $n \in \{1,\dots,50\}$ are
$$
\begin{matrix}
0 &2 &3 &3 &4 &4 &4 &5 &5 &5\\
6 &6 &6 &6 &7 &7 &7 &7 &8 &8 \\
8 &8 &8 &9 &9 &9 &9 &9 &10 &10 \\
10 &10 &10 &10 &11 &11 &11 &11 &11 &11\\
11 &12 &12 &12 &12 &12 &12 &12 &13 &13
\end{matrix}
$$

If you change the condition to $(i+j) \mod n = k$ in constraint $(1)$, the values for $n \in\{1,\dots,50\}$ are instead
\begin{matrix}
0 &2 &3 &3 &4 &4 &4 &5 &5 &5 \\
5 &6 &6 &6 &7 &7 &7 &7 &7 &7 \\
8 &8 &8 &8 &8 &9 &9 &9 &9 &9 \\
9 &10 &10 &10 &10 &10 &10 &11 &11 &11 \\
11 &11 &11 &11 &12 &12 &12 &12 &12 &12
\end{matrix}


A: In this thread I answered a similar question for sumsets. Some of results mentioned in the thread can be applicable to this question. Namely, lower size sumsets bounds for $\Bbb Z$ provide lower bounds for $f_+(n)$  (see the beginning of Qiaochu Yuan’s answer for the definition of $f_+(n)$).:

it seems that in this direction was mainly investigated the 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 am checking the mentioned papers, but I already can say that the results of [Mos] imply that $f_+(n)>\sqrt{\tfrac {2n-2}{1-.0197}}$ for sufficiently large $n$.

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 ﬁve disjoint arithmetic progressions, see the description at p. 6 of Pikhurko’s paper.

Since sums of  distinct elements of $S$ cover the discrete segment $[0, 14t^2 + 10t − 1]$ but a number $8t^2+4t-2$, see the last paragraph of [Pih, p.6], we can add one element to the set $S$ and obtain a set $S’$ such that sums of distinct elements of $S’$ cover the discrete segment $[0, 14t^2 + 10t − 1]$, which follows $f_+(14t^2 + 10t)\le 7t +4$.
This fact provides an upper bound for $f_+(n)$ as follows. Pick the smallest natural $t$ such that $14t^2+10t\ge n$. Then $n\ge 14(t-1)^2+10(t-1)+1=14t^2-18t+5$. Solving the respective quadratic equation, we see that for $n\ge 4$ we have $t\le\tfrac {9+\sqrt{56n-199}}{28}$ and so $$f_+(n)\le 7t+4\le \frac{25+\sqrt{56n-199}}{4}.$$
References
[GN] C. Sinan Güntürk, Melvyn B. Nathanson A new upper bound for finite additive bases, Acta Arithmetica 124 (2006), 235-255.
[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.
[Pih] Oleg Pikhurko Dense Edge-Magic Graphs and Thin Additive Bases.
[Yu] Gang Yu Upper bounds for finite additive $2$-bases, Proc. Amer. Math. Soc. 137 (2009), 11-18.
