Research Frontier and Open Problems

Status: Open research map

The preceding chapters establish the current algebraic core of the Algorizk Research Notes. This chapter marks the boundary between what has been proved, what holds under explicit hypotheses, what may be supported computationally, and what remains open.

Its purpose is not to announce conclusions prematurely. It provides a stable map for future proofs, experiments, implementations, and protocol work.

11.1 Status vocabulary

Every substantial future claim should use one of the following labels.

Established

An established result has a complete proof under the assumptions stated in the result. Its dependencies must also be established or explicitly cited.

Conditional

A conditional result has a complete implication of the form

$$\text{stated hypotheses}⟹\text{stated conclusion}.$$

The implication is proved, but one or more hypotheses may not be known to hold in every field or parameter regime of interest.

Computational

A computational result is verified for a finite, explicitly recorded set of inputs by a reproducible program. It is evidence, not a universal theorem.

Open

An open item is a question, conjecture, missing proof, missing construction, or unresolved complexity or soundness analysis.

These labels describe the logical status of a claim, not its perceived importance.

11.2 Established algebraic core

The following results have been established in Chapters 1–9:

• Boolean vectors index the ordinary monomial degrees below $2^m$;
• the Boolean kernel polynomials form a basis of $\mathbb{F}[X{]}_{<2^m}$;
• the kernel-to-monomial coefficient map is an invertible Boolean transform;
• low degree is characterized exactly by the character space ${\mathsf{CH}}_{m,k}$;
• one-round and repeated coefficient folding satisfy exact algebraic identities;
• repeated folding is a standard multilinear evaluation after the necessary sign correction;
• evaluation on $N$ distinct field points is an isomorphism;
• ${\mathsf{CH}}_{m,k}$ maps exactly onto the corresponding Reed–Solomon evaluation space;
• the local affine butterfly identity preserves degree halving; and
• recursive affine coordinates produce an affine kernel basis with the same Boolean low-degree filtration.

These statements do not require a cryptographic protocol interpretation.

11.3 Established conditional algorithm

Chapter 10 proves the following conditional implication:

$$\begin{array}{c}\text{a compatible affine quadratic domain tower of size }N=2^m\end{array}$$

$$⟹$$

$$\begin{array}{c}\text{affine-kernel evaluation using }\frac{mN}{2}\text{ multiplications}\\ \text{and }\frac{3mN}{2}\text{ additions or subtractions}.\end{array}$$

The recursion, correctness proof, and operation counts are established. The existence of a compatible tower for an arbitrary field and target size is not assumed.

11.4 Results not established by coordinate equivalence

The invertible map

$${\Phi }_D:{\mathbb{F}}^{{\mathbb{B}}_m}⟶{\mathbb{F}}^N$$

identifies kernel coefficient tables with evaluation tables. It also maps ${\mathsf{CH}}_{m,k}$ onto $\mathrm{RS}(D,2^k)$.

However, invertible linear maps do not generally preserve Hamming distance. Therefore none of the following follows from invertibility alone:

• equality of coefficient-space and evaluation-space distances;
• transfer of sparse errors between the two coordinate systems;
• preservation of relative distance under ${\Phi }_D$;
• a proximity gap for folded coefficient tables; or
• robust soundness of a proof protocol.

Any future result of this kind requires a separate theorem with a valid metric argument.

11.5 Open Problem A — Affine tower existence

Let $p$ be an odd prime. Define $M(p)$ to be the largest integer $m$ for which ${\mathbb{F}}_p$ contains an affine quadratic domain tower whose first domain has size $2^m$.

Basic cardinality gives

$$2^{M(p)}\le p-1,$$

because the first domain is partitioned into nonzero pairs $\{\alpha ,-\alpha \}$.

The main questions are:

1. How can $M(p)$ be characterized arithmetically?
2. Which primes attain the largest power of two allowed by cardinality?
3. What lower bounds on $M(p)$ hold for every prime or for a positive density of primes?
4. How does the answer change for finite extension fields?

Finite searches may suggest patterns, but they do not by themselves answer these questions.

11.6 Open Problem B — Constructing towers efficiently

Even when a tower exists, an evaluation algorithm needs the domains, affine parameters, and fiber ordering explicitly.

The constructive problem is to design an algorithm that, given a field and a target depth, either:

• outputs a valid tower with a machine-checkable certificate; or
• certifies that no tower exists within a precisely specified search class.

Relevant complexity measures include:

• field operations;
• quadratic-residuosity tests;
• memory usage;
• deterministic versus randomized running time; and
• preprocessing cost relative to repeated evaluations on the same tower.

A heuristic search is useful computational evidence, but it is not a general construction theorem.

11.7 Open Problem C — Metric comparison

For a coefficient table $\lambda$, define the relative coefficient distance

$${\delta }_{\mathrm{coef}}(\lambda )=\frac{1}{N}{\mathrm{dist}}_H(\lambda ,{\mathsf{CH}}_{m,k})$$

and the relative evaluation distance

$${\delta }_{\mathrm{eval}}(\lambda )=\frac{1}{N}{\mathrm{dist}}_H\left({\Phi }_D(\lambda ),\mathrm{RS}(D,2^k)\right).$$

The open problem is to determine whether useful inequalities between these quantities hold under additional structure on:

• the evaluation domain $D$;
• the error model;
• the coefficient support;
• the affine or ordinary kernel transform; or
• a metric better adapted to the transform.

No universal constant-factor Hamming comparison is currently asserted.

11.8 Open Problem D — Robustness under folding

Chapters 5 and 6 prove exact identities for correctly formed tables. A proximity protocol must additionally analyze corrupted tables.

The central questions are:

1. If a table is far from ${\mathsf{CH}}_{m,k}$, how often can a random fold be close to ${\mathsf{CH}}_{m-1,k-1}$?
2. Which metric should be used before and after folding?
3. How do exceptional challenges depend on the error pattern?
4. Can the analysis be iterated without treating a different nearest codeword independently at every round?
5. What list-size or agreement bounds are required?

An algebraic folding identity is not sufficient to answer these robustness questions.

11.9 Open Problem E — List decoding and proximity gaps

The evaluation image of ${\mathsf{CH}}_{m,k}$ is a Reed–Solomon code, whose evaluation-space distance is known. The desired research direction is to understand proximity tests that respect the kernel and folding structure.

A complete result would need to specify:

• the received-word space;
• the code and metric;
• the agreement or distance threshold;
• the list size;
• the challenge distribution;
• the number of rounds and queries; and
• the final soundness error.

Until all these components are proved together, a claimed proximity gap must remain open or conditional.

11.10 Open Problem F — Transparent post-quantum protocol

The algebraic results suggest a transparent protocol architecture combining:

• kernel or affine-kernel coefficient folding;
• evaluation consistency checks;
• collision-resistant hash commitments;
• random field challenges; and
• a final low-dimensional verification step.

A complete protocol theorem must still provide:

• precise prover and verifier algorithms;
• completeness;
• binding assumptions;
• proximity or knowledge soundness;
• concrete parameters for the target security level;
• round, query, proof-size, and arithmetic counts; and
• a post-quantum security interpretation.

No pairing-based commitment or trusted setup is assumed in this research direction.

11.11 Open Problem G — Interpolation and implementation

Chapter 10 establishes fast forward evaluation on a supplied affine tower. The next algorithmic tasks are:

• derive and verify the inverse recursive interpolation algorithm;
• give exact multiplication, addition, and inversion counts;
• determine which inverses can be precomputed;
• design an iterative memory layout for the fibers;
• compare in-place and out-of-place implementations; and
• benchmark against classical FFT, additive FFT, and general multipoint evaluation baselines.

These are concrete development tasks. They should not be described as completed until code, tests, and reproducible benchmarks are available.

11.12 Open Problem H — Hardware-oriented evaluation

The butterfly structure exposes regular pairs of additions and one multiplication by a domain element. This suggests a hardware pipeline, but an operation count alone is not a hardware performance result.

A credible FPGA or accelerator study must report:

• the target field and representation;
• multiplier and reduction architecture;
• memory bandwidth and layout;
• pipeline depth and initiation interval;
• clock frequency;
• latency and throughput;
• resource utilization;
• power or energy when available; and
• comparisons under matched security and parameter assumptions.

Until such an implementation exists, hardware advantages remain a research and engineering hypothesis.

11.13 Computational-evidence standard

A computational claim may be promoted into these notes only when its record contains:

1. the exact field and parameter range;
2. the definition of the searched object;
3. whether the search was exhaustive or sampled;
4. deterministic code or recorded randomness;
5. independent validity checks for every reported object;
6. software and dependency versions; and
7. a statement limited to the tested range.

For example, an exhaustive search may establish that no object exists inside the enumerated finite search space. It does not establish a general nonexistence theorem for untested primes, depths, or construction families.

Internal notebooks are source material for this process. They are not copied directly into the book.

11.14 Publication gates

Before a result changes status, it should pass the corresponding gate.

Protocol results additionally require a complete security model and soundness analysis. Performance results additionally require reproducible implementation and benchmark methodology.

11.15 Current boundary

The current book provides a working mathematical foundation:

$$\text{Boolean kernel algebra}⟶\text{low-degree character space}⟶\text{folding identities}⟶\text{evaluation correspondence}$$

and, conditionally,

$$\text{compatible affine tower}⟶\text{fast affine-kernel evaluation}.$$

The next research phase begins at tower construction, metric robustness, proximity soundness, interpolation, and implementation. These directions are recorded as open until their required proofs or reproducible evidence are complete.