For fixed $d\geq 2$, let $\tau_d(n)$ be the minimum size of a set $S\subseteq\{0,\ldots,n\}^d$ such that the affine lines determined by pairs of distinct points of $S$ cover the grid. Let $\sigma_d(n)$ be the analogous minimum when every grid point must lie on the closed segment joining two distinct points of $S$. A celebrated result of Alon [GAFA, 1991] proved that $\tau_d(n)$ is of order between $\Omega_d(n^{\alpha_d})$ and $O_d(n^{\alpha_d}\log n)$, where $\alpha_d=\frac{d(d-1)}{2d-1}$, and asked whether the logarithm term is necessary. We prove that $$c_d n^{\alpha_d}\leq\tau_d(n)\leq\sigma_d(n)\leq C_d n^{\alpha_d}$$ for every fixed $d\geq 2$, thereby resolving Alon's problem in a stronger form.
Let $L$ be a fixed set of positive integers. A family $\mathcal{F}\subseteq 2^{[n]}$ is called $L$-differencing if $\lvert A\setminus B\rvert\in L$ for every ordered pair of distinct members $A,B\in\mathcal{F}$. A longstanding conjecture of Frankl, proposed in 1985, asserts that every $L$-differencing family has size at most $\binom{n}{|L|}$. We resolve this conjecture asymptotically for every fixed $L$, and obtain the exact answer in the only case in which the conjectured bound could be tight. (1) If $L\ne [s]$ and $n$ is large, then every $L$-differencing family satisfies $\lvert \mathcal{F}\rvert \le \left(\frac{s}{s+1}+o_L(1)\right)\binom{n}{s}$. (2) If $L=[s]$ and $n\ge 2s-1$, then $\lvert \mathcal{F}\rvert\le\binom{n}{s}$, with equality only for $\binom{[n]}{s}$ and $\binom{[n]}{n-s}$. The first result follows by reducing directed differences to restricted Hamming distances. For the exact result, we develop a new homogeneous polynomial method, which might be of independent interest.