Let $|\cdot|$ denote the usual norm in $\mathbb{Z}^d$. Given a finite subset $S \subset \mathbb{Z}^d$, let $\varphi(S) = \sum_{z \in S}|z|^2$. Given $m \in \mathbb{N}$, what is the size of $\varphi^{-1}(m)$? In particular, a rough upper bound would suffice.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
$|\varphi^{-1}(m)|$ is a coefficient at $x^m$ in the product $$ \prod_{s\in \mathbb{Z}^d} (1+x^{|s|^2}):=F(x) $$ Hence for $0<x<1$ we have $$|\varphi^{-1}(m)|\leq x^{-m} F(x).$$ Minimising RHS in $x$ we get a reasonable upper bound. To be more specific, denote $x=e^{-t}$, $t>0$. Then $$ \log |\varphi^{-1}(m)|\leq mt+\sum_s \log(1+e^{-t|s|^2}). $$ RHS contains a Riemann integral sum for the integral $I=\int_{\mathbb{R}^d} \log(1+e^{-t|x|^2}) dx$. Alas, the Riemann sum is not less than the integral, but let's believe for a moment that they are quite close. Then $I=t^{-d/2} C_0$ for a constant $C_0$, so we get an estimate $mt+C_0t^{-d/2}$. Minimizing by $t$ we get an upper estimate $C(d)m^{d/(d+2)}$.
answered Mar 11, 2015 at 13:57
-
$\begingroup$ Thanks! So just to be clear - to turn this into a proof we would need to estimate how far the integral is from the sum? $\endgroup$– VladimirCommented Mar 11, 2015 at 14:29
-
$\begingroup$ Yes. They are actually close enough by some standard reasoning (function is not too much oscillating.) $\endgroup$ Commented Mar 11, 2015 at 14:41
-
$\begingroup$ This strikes me as too small. In particular, one has a factor of 2^k to account for signs when m is the sum of k nonzero squares. Also, one can pad by zeroes to generate O(k^d) different sets of vectors where each vector has one nonzero component. I expect growth more like exp(m). $\endgroup$ Commented Mar 11, 2015 at 14:53
-
$\begingroup$ @TheMaskedAvenger my final result is an estimate for logarithm, of course $\endgroup$ Commented Mar 11, 2015 at 14:55