# Space-time constraints

$$\def\F{\mathbb F}$$

Goal. Simulate a form of (random access) memory using bivariate polynomials $P\in\F[X,Y]$.

Intuitively, we lay out the memory with time on the $X$ axis and space (addresses) on the $Y$ axis.

## Stack

Start with a simple stack where $P(𝜔_n^i, 𝜔_m^j)$ is the value of stack location $j$ at time $i$.

The initial polynomial is the zero polynomial on our basis $𝜔^j$

$$P(0, Y) = Y^m - 1$$

Note. It looks like we can handle the memory sparsely, both in the polyonmial form and in the merkle trees.

$$L_{m,j}(Y) = \frac{𝜔_m^j}{m} \frac{Y^m - 1}{Y-𝜔_m^j}$$

### Push & Pop

Constraint. (Push). Rotate all elements to the right, add an element $x$. Has the following constraints:

\begin{aligned} P(X, 𝜔_m^{m-1}) &= 0 \\ P(𝜔_n ⋅ X, Y) &= P(X, 𝜔_m ⋅ Y) + x ⋅ L_0(Y) \end{aligned}

Constraint. (Pop). Operate the push constraint in reverse.

### Random access

Constraint. (Compare and swap). Replace the value at $j$ from $a$ to $b$.

\begin{aligned} P(X, 𝜔_m^j) &= a \\ P(𝜔_n ⋅ X, Y) &= P(X, Y) + (b - a) ⋅ L_j(Y) \end{aligned}

The problem here is that we need to encode the $j$ somehow, either in a precomputed polynomial or as a column. Since all usage of $j$ will be in the form $𝜔_m^j$ we will use that instead. the final constraint will look like:

\begin{aligned} P(X, Q(X)) &= a \\ P(𝜔_n ⋅ X, Y) &= P(X, Y) + (b - a) ⋅ \frac{Q(X)}{m} \frac{Y^m - 1}{Y-Q(X)} \end{aligned}

To do. What if $Q(X)$ is not of the form $𝜔_m^j$?

The first constraint has a degree bound of $(\deg P)⋅(\deg Q) = n^2 m$. So far we have only handle constant constraint bounds. How do we LDE test this efficiently?

We could add a temporary value? $t = Q(X), P(X, t) = a$?

In addition, to force $Q(X)$ to be a root of unity, we can add a constraint

$$Q(X)^m = 1$$

which has degree bound $m\deg Q = nm$. Again, how do we LDE-test this efficiently?

## Polynomial composition

Both approaches above hit the problem that we need to low-degree-test an expression of the form $P(Q(X))$. The straightforward approach has degree bound $(\deg P)(\deg Q)$ which is quadratic. This will kill prover performance and more than double proof size.

Goal. Find a way to LDE test polynomial compositions efficiently.

To do. Specify goal more concretely.

https://en.wikipedia.org/wiki/Polynomial_decomposition

https://www.math.mcgill.ca/rickards/PDFs/amer.math.monthly.118.04.358-rickards.pdf

https://www.cs.cornell.edu/~kozen/Papers/poly.pdf

Chebyshev polynomials have the nesting property $T_n(T_m(X)) = T_{mn}(X)$.

https://dspace.mit.edu/bitstream/handle/1721.1/71792/Kedlaya-2011-FAST%20POLYNOMIAL%20FACT.pdf?sequence=1&isAllowed=y https://www.cse.iitk.ac.in/users/nitin/courses/CS681-2016-17-II/pdfs/slides-dwivedi.pdf Evaluates $f(g(x)) \mod h(x)$ in less then $\mathcal O(n^2)$ time using FFTs. => Read. http://users.cms.caltech.edu/~umans/papers/U07.pdf

https://www.cse.iitk.ac.in/users/nitin/courses/CS681-2016-17-II/pdfs/slides-dwivedi.pdf