## n-dimensional recursion

I am trying to set up a recursive function that generates n number of differential equations for Subscript[y, n][t]

This function almost works.

Table[{Subscript[y0, j] = 1}, {j, 50}];(*initial conditions for Subscript[y, n] assuming n<=50*) vars[n_] := {x, Table[Subscript[y, j], {j, n}]}; sol[T_, b_, d_, r_, n_] :=   sol[T, b, d, r, n] =    Flatten[vars[n]] /.     NDSolve[Flatten@{Join[{x'[t] ==            10^7 r - d x[t] - b*x[t]*(Sum[Subscript[y, k][t], {k, n}])},          Table[Subscript[y, j]'[t] == -d Subscript[y, j][t] +             b x[t]*Subscript[y, j][t], {j, n}],          Flatten[Join[{x == 0},            Flatten[Table[{Subscript[y, j] == Subscript[y0, j]}, {j,               n}]]]]]}, Flatten[vars[n]], {t, 0, T}][] sol[i][T_, b_, d_, r_, n_] :=   sol[i][T, b, d, r, n] =    Flatten[vars[n]] /.     NDSolve[Flatten@{Join[{x'[t] ==            10^7 r - d x[t] - b*x[t]*(Sum[Subscript[y, k][t], {k, n}])},          Table[Subscript[y, j]'[t] == -d Subscript[y, j][t] +             b x[t]*Subscript[y, j][t], {j, n}],          Flatten[Join[{x == 0},(*next bit seems to be the problem*)           Flatten[Table[{Subscript[y, j] ==                sol[i - 1][T, b, d, r, n][[j + 1]][T]}, {j, n}]]]]]},       Flatten[vars[n]], {t, 0, T}][] 

The initial condition sol[T, b, d, r, n] works as expected and returns the interpolating functions:

T = 4; b = 10^-7; d = 0.25; r = 0.2; n = 4; sol[T, b, d, r, n]  

And also returns the value at t = T e.g. sol[T, b, d, r, n][]

sol[i][T, b, d, r, n]  does not work for i>0.

It seems that the problem is where the solution from the previous iteration i-1 is used to set the initial conditions for current iterate i, as marked in the code.

I imagine this will be trivial to troubleshoot for someone on here. Any advice is much appreciated.

## N-dimensional generalization of map and reduce?

Is there any conceptual generalization of higher-order functions like map and reduce but for N-dimensional objects (e.g. arrays or tensors)?

For mapping, I guess it would be a point-wise generalization. In the case of reduction, I have more doubts because the iteration is not trivial. Perhaps it would take an additional argument specifying the dimension (or dimensions?) along which the reduction is applied?

Are such higher-order functions defined in algebra? E.g. do they have a specific name and are studied as such?

Posted on Categories proxies

## Is there an algorithm to determine which face of an n-dimensional hypercube is closest to a given point in $O(n\log(n))$?

Given a point in N-dimensional space, I’d like to be able to determine which face of an N-dimensional hypercube of edge length 1 that the point is closest to.

In the 2-dimensional case it’s fairly trivial, you simply split the square along its diagonals:

if (x < y) then     if (x + y < 0) then         // Side 1     else         // Side 2 else     if (x + y < 0) then         // Side 3     else         // Side 4  

In 3-dimensions, this becomes more complex; each face creates a ‘volume’ of points that are closest to it in the shape of a square based pyramid.

Visualisation of the 6 planes that form the 6 pyramids

Of course, given a point, it’s possible to determine which side of the 6 planes it lands on and using that information you can determine which face of the cube is closest. However this would involve running 6 separate checks.

Moving this into higher dimensions, a similar algorithm can be run on hypercubes, however, as the number of faces on a n-cube is $$2^{n-2}{n \choose 2}$$, this quickly becomes computationally very expensive.

However, theoretically a perfect algorithm could cut the search space in half with every check, discarding half the faces each time.

This would give this hypothetical algorithm a runtime of $$O(\log_2(2^{n-2}{n \choose 2}))$$ which can be simplified, if my rate of growth calculations worked out, to $$O(n\log(n))$$

Is my logic correct here; can/does such an algorithm exist?

Posted on Categories proxies

## Counting the Number of Lattice Points in an $n$-Dimensional Sphere

Let $$S_n(R)$$ denote the number of lattice points in an $$n$$-dimensional “sphere” with radius $$R$$. For clarification, I am interested in lattice points found both strictly inside the sphere, and on its surface. I want to count exactly how many such points there are. This count corresponds to the amount of sets of integers that are solutions to the equation $$a_1^2+a_2^2+a_3^2+…+a_{n-1}^2+a_n^2= R^2$$ where the $$a_i$$‘s are required to be integers, not necessarily positive, and sets that differ just by the order of the summands are also considered distinct, i.e for the case $$n=3, R=5$$, the following are both counted: $$3^2+(-4)^2+0^2$$ and $$(-4)^2+0^2+3^2$$. This can also be interpreted as the sum of squares function$$r_d(k)$$ denotes in how many such ways I can write $$k$$ as the sum of $$d$$ squares. This means that $$S_n(R) = \sum_{k=1}^{R^2}r_n(k)$$

I am asking this question as a general one, but I am mostly concerned about the cases of $$n=2, n=3,n=4$$.

In order not to be too lengthy and remain focused, I won’t explain why but summing this way requires to factor each $$k$$ first. This is very time consuming, so I searched for better ways.

For the case of $$n=2$$, which is essentially just the count of lattice points in a circle of radius $$R$$, there is a lot of information – this is known as the Gauss Circle Problem and I have managed to find that $$S_2(R)= 1+\sum_{i=1}^\infty\biggl(\biggl \lfloor\frac{R^2}{4i+1}\biggl \rfloor-\biggl \lfloor\frac{R^2}{4i+3}\biggl \rfloor\biggl )$$For the case of $$n=4$$, I found: $$S_4(R)= 1+8\sum_{k=1}^{R^2}\sum_{d|k \atop {4\nmid d}}d$$ Unfortunately, for the case of a sphere ($$n=3$$), I have found no formula, neither for the count of lattice points inside nor on the surface of the sphere.

Although these formulas do indeed provide the count of lattice points, they are very slow in computational terms, as their running time complexity is $$O(R^2)$$. I was wondering if a more efficient way exists to count the number of such lattice points, perhaps $$O(R)$$ or $$O(R^{1/2+\epsilon})$$, so that I can work with radii as big as $$10^9$$ or even more. I suspect there is a way, but I can’t find it. Not necessarily a different approach to the problem, but rather just a more clever way to reduce the order of the sum. Also, any insight about $$S_3(R)$$ will be appreciated.