Raz proposed a program to prove arithmetic circuit lower bounds through the explicit construction of elusive functions. These are polynomial maps from a low dimensional space to a high dimensional ambient space whose image is contained in no subvariety of low complexity. Here, complexity is prescribed in terms of the dimension and degree of parametric maps into the ambient space defining the subvariety. Elusive functions are abundant: finding explicit ones with parameters typical of generic polynomial maps implies Valiant's hypothesis that VP$\neq$VNP. But no such construction is known. Raz devised elusive functions with weaker parameters to derive explicit degree d polynomials in n variables requiring superlinear circuit size at depth $d=o(\log n)$.

We present a new method to analyse and construct elusive functions, with coordinate maps restricted to monomials. To prove elusiveness, we identify a hitting set of points, each a tuple of roots of unity coupled based on the exponents of the monomial maps. Using Chebotarev's theorem on roots of unity, we show that for every low complexity subvariety, the function evaluated at some point in the hitting set eludes it. For this strategy to work, it suffices that the iterated sumset of a certain set of numbers (derived from the exponents) expands exponentially. We thus reduce open explicit construction problems in elusive functions (entailing complicated polynomial constraints) to purely additive combinatorial ones, whose resolutions imply as yet unknown lower bounds.

Informed by iterated sumset expansion, we devise new elusive functions. We construct explicit elusive curves of exponential degree, resolving an open problem posed by Garg, Makam, Oliveira, and Wigderson as a testament to the difficulty of elusiveness proofs. The exponential degree obstructs the deduction of lower bounds, but even lowering it to subexponential would imply VP$\neq$VNP. We improve Raz's superlinear bound quadratically (with circuit size to input size ratio as the metric) below $o(\log n/\log\log n)$ depths. The degree of our explicit polynomial is comparable to Raz's at the deep end of $o(\log n/\log\log n)$, but much worse at shallower depths. Our methods can also prove rigidity of symbolic matrices, high-rank of symbolic tensors, and more generally find points outside algebraic natural proofs. As an example, we present semi-explicit high border rank tensors over smaller degree number fields than previously known.