Can we count the number of integer lattice points in this case?

Question

Gauss Circle problem gives the number of lattice points lie within a circle of radius $r$. This question points to a reference that estimates the number of lattice points in a $d−$dimensional ball.

$2rd$ represents the number of integer lattice points that have distances only on one coordinate(dimension) like, for example, $(1,0,\dots,0)$ or $(0,r,0\dots,0)$.

Suppose that we have a $d−$dimensional ball around the origin, we want to count the number of integer lattice points that lie within a distance $r$ from the origin where these points should have distances only in no more than $(d/2)$ coordinates and it's distance on the rest of coordinates must equal $0$. i.e if $d=4$ and $r=3$ then what is the number of integer lattice points lie within the ball s.t these points lie in a number of coordinates $≤2$.

Up to the written constraint, we can count the following points $(1,0,0,0),(0,−3,0,0),(0,1,−2,0),(−1,0,0,−2),…$ But I can't consider $(−1,1,0,1)$

For sure I was able to consider $(−1,0,0,−2)$ because this point has distance in only two coordinates and the Euclidean distance to the origin $(0,0,0,0)$ is $5 <(r^2=9)$ where as the point $(−1,1,0,1)$ was not considered because it has distance in three dimensions (against our constraint) although it's distance to the origin $=3<r^2=9$.

Is it possible to enumerate this number? If so, is there a known formula or procedure to compute or bound this number of lattice points? Also, is there a relation between this constrained number and the whole number of lattice points (for example, if $n$ is the constrained number and $N$ is the whole number of integer lattice points then $N>n\geq N/2$).

I asked this question previously here but I didn't receive an answer!

Thanks for any help, hint or a reference.

Answer 1

An exact formula can be given for what you seek in terms of the functions giving point counts for balls. However, those functions are only known to approximate accuracy. The accuracy is good, but there are significant oscillations.

Let $\mathcal{B}_n(r) \subset \mathbb{R}^n$ be the closed ball of radius $r$ centered at the origin.

Consider these functions of $r$:

• $B_n$ where $B_n(r)$ is the number of lattice points in $\mathcal{B}_n(r).$
• $B_{n,m}$ counts lattice points in $\mathcal{B}_n(r)$ which have exactly $m$ non-zero coordinates. SO
• $B_{m,m}$ is the function of $r$ counting lattice points in $\mathcal{B}_m(r)$ with all coordinates non-zero.
• $C_n$ giving what you want, the number of lattice points in $\mathcal{B}_n(r)$ with at least half the coordinates $0.$

Then we have these relations (given below) between the functions. However, for $n \gt 1,$ this gives the the values only approximately.

---

It is nicest to let $r$ be a real variable. Then it is easily explained that $B_n(r)$ is fairly close to the volume $\mathcal{B}_n(r)$. However this volume is a smooth increasing function while $B_n(r)$ is piece-wise continuous with jumps only at $r=\sqrt{k}$ for integers $k$ expressible as the sum of $n$ squares. (This is all integers once $n \geq 4$ ).

Here is a plot of $B_2(r)$ and $\pi r^2$ up to $20.$ The second picture is $B_2(r)-\pi r^2.$ In general, we have a nice, smooth, and relatively good approximate formulas for $B_n,$ but there are oscillations of growing magnitude.

For an example below I will note that $B_2(20)=1257$ which is quite close to $400\pi=1256.6$ however $B_2(18)=1009$ while $ 18^2\pi=1017.9$

Since we can work out that $1+80$ if the $257$ points in $\mathcal{B}_2(20)$ have $0$ or $1$ non-zero coordinate, it turns out that $B_{2,2}(20)=1176.$ We only know that because somehow we had the exact value of $B_2(20).$

---

Here are some easily derived relations. Th equations are exact but the ingredients are not

1. $B_{n,m}=\binom{n}mB_{m,m}$
2. $B_{n}=\sum_{m=0}^nB_{n,m}=\sum_{m=0}^n\binom{n}mB_{m,m}$ so
3. $B_{n,n}=B_n-\sum_{m=0}^{n-1}\binom{n}{m}B_{m,m}$
4. $C_n=\sum_{m=0}^t\binom{n}mB_{m,m}$ where $t=\lfloor \frac{n}2 \rfloor$
5. $C_n \lt \binom{n}{t} B_{t}.$

The last inequality multiplies $\binom{n}{t},$ the number of ways to pick $t$ coordinates which are allowed to be non-negative, by $B_t(r)$ the (approximately known) number of lattice points in $\mathcal{B}_n(r)$ with $0$ in all the other $n-t$ coordinates and possibly some of those $t.$ It is an inequality because $C_n$ is the size of the union of those disks, but they are not disjoint. However, the intersections are small enough, relatively, that the error introduced is perhaps not worse then the error in approximating the $B_n$ by a volume.

I'll note below that the best value we can give for $C_4$ is $6\pi r^2 -16r-5$ so approximating it as $6 \pi r^2$ is not off by much.

---

Here are the first few

$B_{0,0}(r)=1$ since $B_{n,0}(r)=1.$

$B_{1,1}=2r$ so:

$B_{2,2}=B_2-(2B_{1,1}-B_{0,0}) \approx\pi r^2-(4r+1)$

$B_{3,3}=B_3-(3B_{2,2}+3B_{1,1}+1B_{0,0}) \approx \frac43\pi r^3-3\pi r^2+9r+2$

Finally, let us look at your question when $n=4$ with some special attention to $r=20.$

From the formula for the volume of a sphere in $4$ dimensions we know $B_4(r) \approx \frac{\pi^2}{2}r^4$

at $r=\sqrt{383}$ and $r=\sqrt{384}$ the exact values are $727201$ and $727297$ and the respective errors are $+3319.8$ and $-369.2$

It turns out that $B_4(20)=789905$ which is $336.6$ more than the volume of a radius $20$ ball. You ask how many of these $789905$ lattice points have at least half the coordinates equal to $0.$ We will see in a bit that the exact number turns out to be $B_{0,0}(20)+4B_{1,1}(20)+6B_{2,2}(20)=1+160+7056=7217.$

The answer will certainly be less then $6B_2(20)$ which turns out to be $7542.$

Here are the details:

As noted above, it turns out that $B_2(20)=1257$ which is quite close to $400\pi=1256.6$ but might have been over or under that by $8.$

The $1257$ lattice points in a disk of radius $20$ are made of $B_{0,0}(20)+2B_{1,1}(20)+B_{2,2}(20)=1+2\cdot 40+1176.$ There are $\binom42=6$ planes defined by two of the coordinate axes. The intersection of each with the $B_4(20)=789905$ points of the sphere consists of $B_2(20)=1257$ points. The size of the union of these sets is the number you want, which turned out to be precisely $7217.$ Estimating it as $6B_2=7542$ comes out too large since some points are counted multiple times. But the error in doing this is about $4.5\%$

In general, somewhat less than $6B_2(r) \approx 6 \pi r^2$ out of the total of roughly $\frac{\pi^2}2r^4$ lattice points counted by $B_4(r)$ have two or less non-zero coordinates. About the most accurate we can get is $6 \pi r^2 -16r-5.$ So the error is roughly $\frac{8}{3\pi r}$ of the actual value.

Answer 2

Given any subset $S$ of $\{1,\dots,d\}$, let $L_S(r)$ be the set of lattice points within distance $r$ of the origin with the property that their $j$th coordinates, for all $j\notin S$, equal $0$. For example, $(0,1,0,2)$ is an element of both $L_{\{2,4\}}(7)$ and $L_{\{1,2,4\}}(\sqrt5)$ but not an element of either $L_{\{2\}}(7)$ or $L_{\{2,4\}}(2)$. You are wanting to count the number of elements of $$ \bigcup_{\substack{S\subseteq\{1,\dots,d\} \\ \#S\le d/2}} L_S(r); $$ and of course the reason that the answer is not simply $$ \sum_{\substack{S\subseteq\{1,\dots,d\} \\ \#S\le d/2}} \#L_S(r) $$ is because many lattice points are double-counted or worse.

However, this is precisely the type of situation that inclusion–exclusion was designed to solve. The exact number of lattice points you are trying to count is $$ \sum_{\substack{S\subseteq\{1,\dots,d\} \\ \#S\le d/2}} (-1)^{\lfloor d/2\rfloor - \#S} \#L_S(r). $$ Moreover, if $B_{k}(r)$ counts the number of lattice points in a $k$-dimensional ball of radius $r$, then $$ \sum_{\substack{S\subseteq\{1,\dots,d\} \\ \#S\le d/2}} (-1)^{\lfloor d/2\rfloor - \#S} \#L_S(r) = \sum_{k=0}^{\lfloor d/2\rfloor} (-1)^{\lfloor d/2\rfloor - k} \binom dk B_{k}(r). $$ For large $r$ this will be approximately $\binom d{\lfloor d/2\rfloor} B_{{\lfloor d/2\rfloor}}(r) \approx \binom d{\lfloor d/2\rfloor} c_{\lfloor d/2\rfloor}r^{{\lfloor d/2\rfloor}}$, where $c_m = \pi^{m/2}/\Gamma(m/2+1)$. But the point is that there is an exact formula that you can extract whatever information you want from.