These are not Golomb rulers, but *difference bases*. The contrast is that Golomb rulers are a *packing problem* (differences must be *distinct*, but can be as sparse as you like), and difference bases are a *covering problem* (differences must *cover* an interval, but can overlap as much as you like).

Difference bases have been studied at least from 1948, and it seems most of the research is in asymptotic bounds. In fact the list of known concrete values is conspicuously short: OEIS A239308 lists values up to $a(37)=10$, indicating a basis of $10$ elements whose differences cover $[1,37]$. For $N=9$ one can take $A=\{0, 1, 4, 7, 9\}$, achieving $|A|=5$.

The current question asks about lower bounds on $|A|$ with respect to $\sqrt{N}$.

**Answer:** The proposed bound $\sqrt{2N}$ is not tight. I think the first nontrivial lower bound was $(1.5570\ldots)\sqrt{N}$ by Rédei and Rényi in 1948 (cited by Erdős and Gál; I haven't seen the original). Leech (1956) improved it to $(1.5602\ldots)\sqrt{N}$. Recently Bernshteyn and Tait (2019) showed that Leech's bound could be improved further (at least "by $\epsilon$") but they did not explicitly show how much.

Further note: A similar MO question is here. In that question, it is required that the differences cover $N$ *consecutive integers* (not necessarily $[1,N]$). But note that if $[1,N]$ is covered by $A-A$, then in fact $2N+1$ consecutive integers $[-N,N]$ are covered, so the problems are very closely linked. (See also Fedor Petrov's comment there.)

## Bibliography

*Erdős, Pál; Gál, S. A.*, On the representation of $1,2,\ldots,N$ by differences, Proc. Akad. Wet. Amsterdam 51, 1155-1158 (1948). ZBL0032.01302.

*Leech, John*, **On the representation of $1, 2,\ldots, n$ by differences**, J. Lond. Math. Soc. 31, 160-169 (1956). ZBL0072.03401.

*Bernshteyn, Anton; Tait, Michael*, **Improved lower bound for difference bases**, J. Number Theory 205, 50-58 (2019). ZBL07101901.

naively provemean? Does it meanprove? $\endgroup$5more comments