HTML reading edition · 47 source pages · Open the source PDF

Arithmetisation of computation via polynomial semantics for first-order logic

Murdoch J. Gabbaya

Abstract. We propose a compositional shallow translation from an impredicative first-order logic with equality, into polynomials; that is, we give a direct, compositional, arithmetic notion of first-order logic validity.

Arithmetisation means translating validity of some assertion ϕ of a model M, into some property RM of a polynomial P(ϕ, M), such that (to a high degree of certainty) ϕ is valid in M if and only if RM holds of P(ϕ, M). Arithmetisation is widely used in cryptography, because many cryptographic protocols work by exploiting properties of finite fields to prove assertions like “R holds of a polynomial P” — a typical property R is ‘has roots in 1, . . . , kM’, where kM is determined by the cardinality of M.

Meanwhile, first-order logic is a simple but expressive language for specifying and reasoning about computation. In particular, it is easily powerful enough to express inductive definitions, Turing-complete computation, and correctness properties thereof. We can think of first-order logic as a high-level, virtual-machine-independent model of reasoning and computation.

Techniques already exist to arithmetise computation by coding it in an abstract machine whose computation has been arithmetised by hand; i.e. by a deep embedding in some preconstructed monolithic cryptographic artefact. What distinguishes our translation is its shallowness, compositionality, and uniform treatment of logical connectives: it translates logical connectives directly to operations on polynomials, without a deep encoding in an abstract machine.

The translation is deceptively straightforward: truth maps to 0, false maps to any strictly positive number, conjunction and universal quantification map to +, and disjunction and existential quantification map to ∗. Yet, we shall see that the outcome is surprisingly powerful and expressive.

Keywords: First-order logic · arithmetisation · verifiable computation · verifiable logic · cryptography · succinct proofs · zero-knowledge proofs · polynomial semantics

This work is licensed under a “CC BY 4.0” license.

Date of this document: 2026-02-11.

1 Introduction

We take a step towards unifying mathematically structured programming (by which we mean ‘computation that is specified using logic’) with cryptographically verifiable computation (meaning ‘executions that can be cryptographically verified’). We do this by giving

1. a compositional, shallow translation of first-order logic to polynomials (Figure 2),

2. a sound and complete translation of logical validity (i.e. predicates being true) to corresponding polynomial equalities (Theorems 2.4.4 and 4.2.7), and

3. an outline of what it means to give succinct proofs (in the cryptographic sense) of the resulting polynomial equalities.

Schemes with this effect exist for von Neumann style abstract machines (a brief but clear survey is in [Lam24]), for logic circuits [DFGK14, LCL+24], and even for LISP [ABG+23] (reference list not exhaustive).1 Yet first-order logic has as good a claim as any to be a universal language of mathematics — and in particular it is a commonly and successfully used as a high-level language for specifying computation. To our knowledge, a compositional semantics for FOL has not yet been given in polynomials.

We summarise what this means and why it matters. This summary is aimed not only at cryptographers but also at readers from a logic and computation background, to provide some context:

Boolean circuits contrasted with arithmetic circuits

Logic uses Boolean circuits: combinations of and, or, and not operating on variables that each hold one bit of information: true or false. Because and and or distribute over one another, and because not satisfies de Morgan dualities, Boolean circuits have a normal form called a disjunctive normal form.

Cryptography uses arithmetic circuits:2 combinations of +, ∗, and x ∈ℤ operating on variables that hold numbers (either from a finite field or possibly just integers). Because ∗ distributes over + (i.e. x ∗ (y + z) = x ∗y + x ∗z) arithmetic circuits also have a normal form: polynomials, as familiar e.g. from maths in school.

Polynomials are very expressive: they can represent functions (by interpolation [SW22, Chapter 9]3), vectors of integers (by evaluating at {1, . . . , n} where n is the length of the vector), multisets (by identification with their multiset of roots), and they can be composed. Polynomials over integers can be evaluated to numbers, and this has unexpected implications including the Schwartz-Zippel lemma [Tha22, Lemma 3.3, Subsection 3.4] (see also a clear historical discussion [Lip09]).

Propositions in disjunctive normal form are not quite as expressive as polynomials, but they have excellent properties: distributivity of and over or and of or over and; de Morgan duality between true and false; and bitwise number representation which are the basis of computer chips;4 and an extremely well-developed theory which includes logic (including first-order, higher-order, and matching logics), declarative programming languages, type-checkers, model-checkers, SAT solvers, formal verification tools, and moving on from there to dependent type theories, modal logics (like TLA+), model theory, and more.

Mathematically structured programming contrasted with cryptography

Mathematically structured programming (MSP) is an approach to programming, based on logic, that tries to minimise the distance between a program and its specification, such that (ideally) the specification is the program and is directly executable, without requiring the programmer to code up a realisation in a lower-level programming language.5

Benefits include (arguably) easier verification, and greater productivity, because the code is kept close to its logical intention. Disadvantages include lower efficiency: it can sometimes be harder to write high-level code that runs quickly on native silicon, by which I mean that the high-level code compiles to efficient low-level instruction sequences suitable for execution on physical (usually silicon-based) computer processing chips. In polynomials it may be that a higher-level MSP-based approach is actually more efficient.6

Cryptography has historically been about secure and verifiable communication (think: encryption and error-correcting codes); but with the rise of distributed systems, cloud computing, and layer 2 blockchains, the focus of interest in cryptographic techniques has shifted and broadened to include secure and verifiable computation. Thus we see modern interest in applications such as succinct proofs of executions, fully homomorphic encryption, multiparty computation, zero knowledge computation, garbled circuits, and more.

The Unique Selling Point

First-order logic is a simple yet powerful logic which has as good a claim as any logic to be a universal (or at least a canonical) language of mathematics. Thanks to this simplicity and power, it is heavily used in mathematically structured programming. Thus, giving a compositional shallow mapping of first-order logic predicates to polynomials has as good a claim as any to being a canonical simple and high-level, and yet potentially very practical, treatment of verifiable computation.

Note that our mapping encodes semantics and validity, not syntax and derivability. In particular, it would be mistaken to assume that this paper works by encoding the syntax of FOL and the structure of well-formed derivation trees into arithmetic circuits. This paper takes a semantic approach that is arguably simpler; see Remark 6.3.3 for more discussion, with an example.

We will see how we can write specifications in first-order logic, compile them to polynomials, and evaluate them there. The translation has low overhead, and it bridges the gap between the abstractness of logic and having direct access to the underlying polynomials. Because our translation is very compositional, we will be able to compose simple specifications to make more complex ones. We hope this will inform both concrete applications as well as new research in mathematical logic.

Who should read this paper

I hope that practitioners will be interested in the ideas in this paper and think about basing practical systems on them. For such readers, the use of logic in MSP style may be new, but we will explain it clearly and with examples. I would argue that this application of logic is not particularly difficult — this is not rocket-science grade logic, it is just propositions and some easy quantifiers — and this is worth looking into because it will yield dividends in simplicity, and offers a promise of reductions in engineering effort and risk. Shorter, simpler, and safer: pick three!

The reader with a logic background should also find plenty of food for thought and future research. There is a new polynomial-based denotation, potential for the reader to develop their own tailored logics based on the same ideas (classical, non-classical, and resource-sensitive), and there are some interesting things going on in our applications having to do with use of reflection, truth-modalities, and more (see Remark 6.1.1). The use of cryptography, if this is unfamiliar to the reader, is clearly signposted and clearly explained, and even if the reader prefers to just focus on the logic, this paper should still be entirely clear.

2 Polynomial semantics for FOL

2.1 Some background on polynomials

We recall some standard definitions and notations. We start off very simply:

Notation 2.1.1

We will be interested in ℤ (integers), ℕ (nonnegative whole numbers), and ℚ (rationals).

We may use subscripts to indicate ranges, writing e.g. ℕ≥0 (which is just ℕ), ℕ≥1 (strictly positive whole numbers), ℚ≥0, and so on.

For n ≥ 0 we may write

1..n = {1, . . . , n} ⊆ℕ.

If n = 0 then by convention 1..n = ∅.

Note in particular that ℕ = {0, 1, 2, . . . }; as is standard in computer science, we start counting at 0, not 1. However, in keeping with standard usage in mathematics, we will start indexing matrix rows and columns from 1, not 0.

Definition 2.1.2

For the purposes of this paper, a rational univariate polynomial (or just polynomial for short) is an element P ∈ℚ[X], where X is a variable.

Thus, P ∈ℚ[X] is a formal sum of powers of X. For example 0, 1 + X, and X2 are all polynomials.

Polynomials can be added and multiplied in the usual way. For example, (1 + X) ∗ (1 −X) = 1 −X2.

Remark 2.1.3

Definition 2.1.2 might seem simple, but for clarity we note a distinction between expressions denoting polynomials, and polynomials.

For example: (1 + X) ∗ (1 −X) is a polynomial expression. It denotes the polynomial 1 −X2, but is not identical to it.

So given P, Q ∈ℚ[X], when we write P ∗Q the reader should understand this polynomial expression to mean ‘that polynomial in ℚ[X] obtained by performing a polynomial multiplication of P and Q’, unless stated otherwise.

Polynomial interpolation in Definition 2.1.4 describes a standard method for using a polynomial to express a vector [SW22, Chapter 9].7

Definition 2.1.4 (Polynomial interpolation).

Suppose ln ≥ 0 and (a1, . . . , aln) ∈ℤln is a ln-tuple of integers.8

1. Say that a polynomial P ∈ℚ[X] interpolates (a1, . . . , aln) when P(i) = ai for each i ∈ 1..ln.

2. Recall that every ln-tuple of integers (a1, . . . , aln) can be interpolated by a unique polynomial interpolant

itplnt(a1, . . . , aln) ∈ℚ[X]

of degree ln−1 (at most).9 Thus, itplnt(a1, . . . , aln)(i) = ai for i ∈ 1..ln.

Notation 2.1.5 (Instantiation).

Suppose P, Q ∈ℚ[X] are polynomials. Write P(Q) for the polynomial obtained by instantiating X to Q in P.10 For example if P = X + 1 and Q = 2 ∗X then

P(Q) = 2 ∗X + 1.

In the case that Q is just a number x ∈ℚ, then we may identify this with the number obtained by instantiating X to x and evaluating the result using arithmetic. For example:

(X ∗(X + 1))(6) = 6 ∗(6 + 1) = 42.

It will always be clear what is intended.

2.2 The syntax of our logic (with examples)

Remark 2.2.1

Our goal in this paper is to define a logic, give it a semantics in ℚ[X], and explore the properties of this semantics. We will:

1. define the formal syntax of terms and predicates in Definition 2.2.3;

2. discuss some intuitions in Remark 2.2.4;

3. define the polynomial semantics for our formal syntax in Definition 2.3.2;

4. discuss the semantics in Remark 2.3.5; and

5. prove a soundness and completeness result in Theorem 2.4.4.

Remark 2.2.2

Note that in the interpretation we are about to build in Figure 2, 0 represents truth and any non-zero value represents false; furthermore ∧ and ∀ (conjunction and universal quantification) map to + (addition), and ∨ and ∃ (disjunction and existential quantification) map to ∗.

If the reader is used to thinking of truth as 1 and false as 0, as is traditional in logic circuits, then be careful: everything below will be flipped with respect to what you initially expect. Our motivation for representing truth by 0 is that it gives us Theorem 2.4.4.11 More on this in Remarks 2.3.5 and 2.4.5.

t ::= X | q | t + t | t −t | t ∗t | len(C) | reify(ϕ) (q ∈ℚ, C ∈MatrixVar)| Ci(t) (i ∈1..arity(C)) ϕ, ψ ::= ⊤| ⊥| t = t | ϕ ∧ϕ | ϕ ∨ϕ | ∀CX.ϕ | ∃XC.ϕ | t < Ci | t > Ci(i ∈1..arity(C))

The grammars above are in BNF style, such that ϕ to the right of ::= represents any predicate. In particular, ϕ ∧ϕ is not a typo; it denotes a conjunction of two (possibly non-equal) predicates. Similarly the two t in t = t denote two (possibly non-equal) terms. 1..arity(C) denotes the set {1, 2, . . . , arity(C)} ⊆ℕ.

Figure 1: Syntax of terms and predicates (Definition 2.2.3(3))

Definition 2.2.3 (Syntax of terms and predicates).

1. Fix one index variable symbol X.

2. Fix a set of matrix variable symbols C, D ∈ MatrixVar. To each matrix variable symbol we associate a fixed but arbitrary arity arity(C) ∈ℕ≥1.

3. Define terms and predicates inductively as in Figure 1. In that Figure:

(a) i ranges over whole numbers between 1 and the arity of C inclusive, or in symbols:

i ∈1..arity(C).

(b) This is just formal syntax; we give it meaning later in Figure 2. In particular: Ci, Ci(t), len(C), and reify(ϕ) are just formal syntax.

Remark 2.2.4

We give some intuitive discussion of the syntax in Definition 2.2.3:

1. The index variable symbol X is the (unique) variable of the polynomial semantics.12 Terms and predicates will map to ℚ[X] (polynomials over X), as per Figure 2.

2. Intuitively a matrix variable symbol C ∈ MatrixVar ranges over all integer matrices of size arity(C) × ln, for all ln ∈ℕ≥1. Using interpolation (Definition 2.1.4) we can also think of C as ranging over elements of ℚ[X]arity(C) × ℕ≥1, where the first component is an arity(C)-tuple of polynomials over ℚ[X], and the second component is the n ≥ 1 that tells us how to reconstruct the matrix by considering the values of those polynomials on the set 1..n.

3. Terms let us build elements of ℚ[X].
The intuition of Ci(t) is an interpolating polynomial for the ith row of C, applied to t (more on this below). The intuition of len(C) is the number of columns in C (its length). The intuition of reify(ϕ) is to treat ϕ as a number (this makes the logic impredicative; we fold predicates back down into terms).

4. Predicates are based on first-order logic. There is equality (of terms) but no negation (because negation is expressible; see Subsection 4.2.2). Intuitively, quantification ∀CX quantifies over X ranging over whole numbers from 1 to the number of columns in the matrix denoted by C; so if C denotes an arity(C) × ln matrix,

then ∀CX.ϕ checks ϕ(1), ..., ϕ(ln), where ϕ(x) is the value of (some polynomial denotation which we have not yet constructed of) ϕ for X instantiated to x ∈ 1..ln.

5. The intuition of the range checks t < Ci and t > Ci is to statically check that elements of the ith row of C takes values greater than or less than t respectively. We use this later to statically check for out-of-bounds pointer errors (see the discussion in Examples 3.2.8 and 3.2.9), and we make further use of this in Section 4.

Example 2.2.5

We give some examples of the syntax in action (even if we have not yet assigned it any formal meaning, we can illustrate how it is supposed to be used). Assume three matrix variable symbols:

1. neg with arity(neg) = 2.

2. add with arity(add) = 3.

3. pos with arity arity(pos) = 1.

Then we can write some easy predicates:

1. ∀negX.neg2(X) = (−1) ∗ neg1(X).

2. ∀addX.add3(X) = add1(X) + add2(X).

3. 0 < pos1.

Intuitively, we are supposed to read these predicates as follows:

1. neg is (= denotes) a matrix with two rows, and the Xth entry in row 2 is (as per the predicate) supposed to be the negation of the Xth entry in row 1, like this:

(0 1 20 −1 −2)

2. add is a matrix with three rows. Entries in row 3 are (as per the predicate) supposed to be the sum of the entries in rows 1 and 2, like this:

0 1 22 1 02 2 2

3. pos is a matrix with just one row, which should consist entirely of strictly positive numbers, like this:

(3 2 1)

In terms of intuition, this is all straightforward.13

We do not have a notion of validity yet, so all of the above is just intuition. Once we have defined validity, we will come back to this; see Example 2.3.4.

Remark 2.2.6

We make a few comments on some simple (non)redundancies in the syntaxes of terms and predicates:

1. Subtraction in terms is redundant: we can just express t −t′ as t + (−1) ∗t′.

2. ⊤ and ⊥ are redundant: we can just express ⊤ as 0 = 0, and ⊥ as 1 = 0.

3. If we admit a unary predicate-former isZero(t) with semantics ⟦isZero(t)⟧ς = ⟦t⟧2 ς, then ⊤, ⊥, and t −t′ become expressible as

⊤= isZero(0), ⊥= isZero(1), and (t = t′) = isZero(t −t′).

4. Negation does not appear explicitly in the syntax or semantics of Figures 1 and 2. Surprisingly, negation is expressible in the rest of the logic: see Subsection 4.2.2.

See also Remark 2.4.6.

⟦X⟧ς = X ⟦q⟧ς = q (q ∈ℚ)⟦t + t′⟧ς = ⟦t⟧ς + ⟦t′⟧ς⟦t −t′⟧ς = ⟦t⟧ς −⟦t′⟧ς⟦t ∗t′⟧ς = ⟦t⟧ς ∗⟦t′⟧ς⟦Ci(t)⟧ς = itplnt(ς(C)i)(⟦t⟧ς)⟦len(C)⟧ς = len(ς(C)) ⟦reify(ϕ)⟧ς = ⟦ϕ⟧ς⟦⊤⟧ς = 0 ⟦⊥⟧ς = 1⟦t = t′⟧ς = (⟦t⟧ς −⟦t′⟧ς)2⟦ϕ ∧ϕ′⟧ς = ⟦ϕ⟧ς + ⟦ϕ′⟧ς⟦ϕ ∨ϕ′⟧ς = ⟦ϕ⟧ς ∗⟦ϕ′⟧ς⟦ ∀CX.ϕ⟧ς = ∑x∈1..len(ς(C)) ⟦ϕ⟧ς(x)⟦ ∃CX.ϕ⟧ς = ∏x∈1..len(ς(C)) ⟦ϕ⟧ς(x)⟦t > Ci⟧ς ={ 0 if ∀j ∈1..len(ς(C)).(⟦t⟧ς > ς(C)i,j)1 otherwise⟦t < Ci⟧ς ={ 0 if ∀y ∈1..len(ς(C)).(⟦t⟧ς < ς(C)i,j)1 otherwise x ⊨ς ϕ ⇐⇒⟦ϕ⟧ς(x) = 0

Negation is expressible using the rest of the logic: see Subsection 4.2.2.

Figure 2: Polynomial semantics for terms and predicates (Definition 2.3.2)

Notation 2.2.7

We set up some convenient abbreviations, writing:

Ci < t for t > Cit ≤Cifor t −1 < CiCi ≤t for Ci < t + 1t < Ci < t′for (t < Ci) ∧(Ci < t′)t ≤Ci ≤t′for (t −1 < Ci) ∧(Ci < t + 1).

Note that this is meaningful because when we build our semantics, our notion of interpretation in Definition 2.3.2(1) will evaluate matrix variable symbols C to integer matrices.

There is not much to this otherwise: we could also just as well take the notation above as primitive in our syntax from Figure 1, and interpret ≤ (a binary predicate symbol in our formal syntax) using ≤ (the binary predicate ‘less than or equals’ on numbers, which returns a truth-value) in Figure 2, alongside interpreting < (the predicate symbol) using < (the predicate ‘strictly less than’).

2.3 The semantics (with examples)

We are now ready to define a semantics in polynomials for the syntax from Definition 2.2.3.

Some notation will be useful for Figure 2 and Definition 2.3.2:

Notation 2.3.1 (Some basic matrix syntax).

Suppose M is a matrix. Then:

1. We may write len(M) for the number of columns in M, and we may call this the length of M.

2. We may write Mi for the ith row in M, which is a vector of length len(M).

3. As usual, we may write Mi,j for the i, j-th element in M; i is the row number and j is the column number.

Definition 2.3.2 (Polynomial semantics).

1. An interpretation ς assigns to each matrix variable symbol C ∈ MatrixVar with arity arity(C) ∈ℕ≥1 an arity(C) × n integer matrix (= having elements from ℤ). Using interpolation (Definition 2.1.4) the reader can also think of ς(C) as a vector of arity(C) many polynomials in X, along with a number n encoding the information that we care about the values of these polynomials on 1..n.

2. Given an interpretation ς, define polynomial semantics

⟦t⟧ς ∈ℚ[X] and ⟦ϕ⟧ς ∈ℚ[X]

for terms and predicates as in Figure 2. See Remark 2.3.5 below for exposition on the notation and design. If ς is irrelevant (e.g. because no matrix variable symbols are mentioned), we may drop the subscript ς and write ⟦t⟧ς just as ⟦t⟧, or ⟦ϕ⟧ς just as ⟦ϕ⟧. For example, we may write ⟦2 = 0⟧ = 4.

3. Given x ∈ℚ, define a judgement by

x ⊨ς ϕ means ⟦ϕ⟧ς(x) = 0,

as per Figure 2. Judgements return truth-values (‘true’ or ‘false’).14

4. If x or ς is irrelevant in x ⊨ς ϕ (e.g. because ϕ is fully-quantified, or mentions no matrix variable symbols) then we may omit it, writing

⊨ς ϕ or x ⊨ϕ or even just ⊨ϕ.

When x ⊨ς ϕ we will call ϕ valid (in the context of x and ς). If x and/or ς is irrelevant, we may just call ϕ valid.

Remark 2.3.3

Definition 2.3.2 is written in the language of logicians. It is straightforward to map this to language that may be more familiar to cryptographers:

1. The predicate ϕ corresponds to what in a cryptographic proof-scheme is called the instance. This defines the problem to be solved and is known to the prover and the validator.

2. The interpretation ς, which maps matrix variable symbols to matrices — equivalently: to interpolating polynomials — corresponds to the witness. This information is known to the prover, but not necessarily to the validator.

3. The validator and prover agree on ϕ, and — on provision of a cryptographic proof-scheme — the prover succinctly or in zero knowledge would prove (in the cryptographic sense) that it knows a witness ς that makes the instance valid.15

The reader can find overviews in [Sch11] and [Tha22]. The choice (and if necessary, the design) of proof-schemes is not monolithic, and may depend on the structure of ϕ — e.g. DNF (disjunctive normal form), Horn clause, etc — and on the intended use-case (succinctness, zero knowledge, rational polynomials vs. polynomials over finite fields, etc). For different choices, different proof-schemes making different trade-offs may be appropriate.

Example 2.3.4

We now use Figure 2 to translate the predicates from Example 2.2.5 into polynomials. Recall that we assumed three matrix variable symbols with associated predicates — since we now have a notion of validity, we will call these validity predicates — as follows:

1. arity(neg) = 2 and validity predicate χneg = ∀negX.neg2(X) = (−1) ∗ neg1(X).

2. arity(add) = 3 and validity predicate χadd = ∀addX.add3(X) = add1(X) + add2(X).

3. arity(pos) = 1 and validity predicate 0 < pos1.

We intend these to model negation, addition, and the property of a number being positive.

Given an interpretation ς, the translations of these validity predicates are polynomials

⟦χneg⟧ς, ⟦χadd⟧ς, ⟦χpos⟧ς ∈ℚ[X]

as per Figure 2 as follows:

⟦χneg⟧ς = ∑x∈1..len(ς(neg))(itplnt(ς(neg)2)(x) −(−1) ∗itplnt(ς(neg)1)(x))2⟦χadd⟧ς = ∑x∈1..len(ς(add))( itplnt(ς(add)3)(x) −)2

(itplnt(ς(add)1)(x)+itplnt(ς(add)2)(x))

⟦χpos⟧ς ={ 0 if every entry in ς(pos) is > 01 if some entry in ς(pos) is ≤0

Let us unpack some of the notation above. We consider just the first clause (the second and third are no different): neg is a matrix variable symbol (a symbol in our syntax from Figure 1); ς(neg) is a matrix (as per Definition 2.3.2(1)); and itplnt(ς(neg)1) is a polynomial interpolating the first row of that matrix at 1, 2, ..., len(ς(neg)) where len(ς(neg)) is simply the number of columns in that matrix.

Note that none of these polynomials have X free in them, so in fact they are just numbers. Thus, following Definition 2.3.2(4) the predicates are valid in the context of ς when that number is 0, and they are invalid when that number is strictly greater than 0.

The reader can check that the predicates are valid of ς, precisely when ς satisfies the conditions that we would intuitively expect — as spelled out in Example 2.2.5 — based on reading the predicates. This observation will be formalised in our soundness and completeness result in Theorem 2.4.4.

Remark 2.3.5

Some comments on Figure 2:

1. ⊤ maps to ⟦⊤⟧ς = 0 and ⊥ maps to ⟦⊥⟧ς = 1. Conjunction and universal quantification map to addition, and disjunction and existential quantification map to multiplication (cf. also Remark 2.4.5). Consequently we can say:

In our denotation, ‘zero’ means ‘true’ and ‘nonzero’ means ‘false’.

This might be confusing because usually (e.g. in logic gates) 1 means ‘true’ and (just) 0 means ‘false’, but setting things up as we do gives us Theorem 2.4.4.

2. The semantics maps terms and predicates to polynomials over X. So for example, the clause ⟦X⟧ς = X says that the X denotes itself.

3. Similarly the clause ⟦q⟧ς = q says that q ∈ℚ denotes itself.

4. The clause ⟦Ci(t)⟧ς = itplnt(ς(C)i)(⟦t⟧ς) implicitly assumes i ∈ 1..arity(C), since as per Definition 2.2.3(3a) and Notation 2.3.1(2) it would make no sense to talk about Ci or ς(C)i otherwise.

5. We break down the clause ⟦Ci(t)⟧ς = itplnt(ς(C)i)(⟦t⟧ς), as follows:

• ς(C) is an integer matrix with arity(C) rows and len(ς(C)) columns. For brevity we may write

C = ς(C).

Note that the number of rows in C must be arity(C); but the number of columns in C is determined by the choice of ς.

• As per Notation 2.3.1(2), Ci denotes the ith row of C, which is a vector of len(C) integers.

• itplnt(Ci) = P is a polynomial in X that interpolates the vector Ci at values 1, . . . , len(C), as per Definition 2.1.4.

• P (⟦t⟧ς) is P instantiated at ⟦t⟧ς, as per Notation 2.1.5.

6. Reading the previous point, the reader might ask why we bother with matrices at all. Why not just let ς(C)i be a polynomial? Because a matrix and its interpolant are not the same thing, if we care about bounds (which we do); a vector has a length, and a polynomial a priori does not. For example, the same polynomial X interpolates many distinct vectors, including (1), (1, 2) and (1, 2, 3).16

Remark 2.3.6

Some comments on Definition 2.3.2:

1. Recall that ς(C) in Definition 2.3.2(1) is an integer matrix C with arity(C) rows and n columns. The number of rows in C is determined by arity(C), but its number of columns depends on ς.

2. Interpretations ς map matrix variable symbols to integer matrices. They do not instantiate the (single) variable symbol X. Furthermore, although we call ς(C) a matrix, we use it as a two-dimensional array (no matrix multiplication, for example). If every time we write ‘integer matrix’ the reader reads ‘two-dimensional array with integer entries’, then no harm will come of it.

3. In Definition 2.3.2(2), ⟦ϕ⟧ς is a polynomial in X — it is not a truth-value. For example,

⟦X = 2 ∗X⟧ς = X2

(there are no matrix variable symbols here so the choice of ς does not matter).

4. In Definition 2.3.2(3), x ⊨ς ϕ is a truth-value — it is not a polynomial. For example,

0 ⊨ς X = 2 ∗X is true, and 1 ⊨ς X = 2 ∗X is false.

5. The denotation of universal quantification ∀ is a summation, like the denotation of ∧. However, ∀ cannot be emulated in the logic by repeated ∧, because the length of the summation depends on the number of columns in the matrix ς(C), which varies depending on the choice of ς. So universal quantification has its own distinct identity.

6. A design path which we do not explore in this paper is that our denotation is compatible with notions of ‘logical implication’ P =⇒Q and ‘logical equivalence’ P ⇐⇒Q on polynomials P, Q ∈ℚ[X], such that

P =⇒Q when ∀x∈ℚ.P(x) = 0 =⇒Q(x) = 0 andP ⇐⇒Q when ∀x∈ℚ.P(x) = 0 ⇐⇒Q(x) = 0.

Note that P =⇒Q does not quite mean the same thing as P | Q (P divides Q), because the multiplicities of the roots in P may differ from those in Q. Similarly, P ⇐⇒Q does not quite mean the same thing as P = Q. For example:

(X −1) ⇐⇒(X −1) ∗(X2 + 1) and (X −1) ⇐⇒(X −1)2.

We do not explore these notions of implication and equivalence explicitly in what follows, but they are implicit in much of the maths; exploring this explicitly is future work. For now, it seems to be more useful to explore a technically different design path and consider a complementation operation ∼ϕ; see Notation 4.2.6 and Theorem 4.2.7.

2.4 Soundness and completeness

Definition 2.4.1

Call a polynomial P ∈ℚ[X] nonnegative when P(x) ≥ 0 for every x ∈ℚ.

Lemma 2.4.2

Suppose ϕ is a predicate and ς is a valuation and x ∈ℚ.

Then ⟦ϕ⟧ς is a nonnegative polynomial (Definition 2.4.1).

Proof

By a routine induction, following Figure 2:

• ⟦⊤⟧ς = 0 and ⟦⊥⟧ς = 1. We note that 0 and 1 are nonnegative.

• ⟦t = t′⟧ς = (⟦t⟧ς − ⟦t′⟧ς)2. It is a fact of arithmetic that this is a nonnegative polynomial, because it is a square.17

• ⟦ϕ ∧ϕ′⟧ς = ⟦ϕ⟧ς + ⟦ϕ′⟧ς and ⟦ϕ ∨ϕ′⟧ς = ⟦ϕ⟧ς ∗ ⟦ϕ′⟧ς. We observe that the sum and product of two (by inductive hypothesis) nonnegative polynomials, is nonnegative.

• As per Figure 2, ⟦∀CX.ϕ⟧ = ∑x∈1..len(ς(C)) ⟦ϕ⟧ς. We observe that this is a sum of (by inductive hypothesis) nonnegative polynomials, and so it is also nonnegative. Similarly for ∃CX.ϕ.

• ⟦t < Ci⟧ς and ⟦Ci < t⟧ς are equal to 0 or 1, and both are nonnegative.End of proof

Remark 2.4.3

Lemma 2.4.2 is interesting because it suggests that we can identify the nonnegative polynomials in ℚ[X] as having logical content, in the sense that these can be the denotations of predicates; in contrast to the class of all polynomials in ℚ[X], which can be the denotation of terms but not necessarily of predicates.

Theorem 2.4.4 (Soundness & completeness).

Suppose ϕ and ϕ′ are predicates, and t and t′ are terms, and ς is a valuation and x ∈ℚ. Then:

1. x ⊨ς ⊤ and x ⊭ς ⊥

2. x ⊨ς t = t′ if and only if ⟦t⟧ς(x) = ⟦t′⟧ς(x).

3. x ⊨ς ϕ ∧ϕ′ if and only if x ⊨ς ϕ ∧x ⊨ς ϕ′.

4. x ⊨ς ϕ ∨ϕ′ if and only if x ⊨ς ϕ ∨x ⊨ς ϕ′.

5. x ⊨ς ∀XC.ϕ if and only if x′ ⊨ς ϕ for every 1 ≤ (x′ ∈ℕ≥1) ≤ len(ς(C)).

6. x ⊨ς ∃XC.ϕ if and only if x′ ⊨ς ϕ for some 1 ≤ (x′ ∈ℕ≥1) ≤ len(ς(C)).

7. x ⊨ς t < Ci if and only if every entry in the ith row of ς(C) is strictly greater than ⟦t⟧ς.18

8. x ⊨ς Ci < t if and only if every entry in the ith row of ς(C) is strictly less than ⟦t⟧ς.

Proof

We consider each part in turn, unpacking Figure 2. The argument is just by routine arithmetic:

1. x ⊨⊤ when 0 = 0, which is true. x ⊨⊥ when 1 = 0, which is false.

2. x ⊨t = t′ when (t −t′)2(x) = 0. By elementary facts of arithmetic, this is if and only if t(x) = t′(x).

3. x ⊨ϕ∧ϕ′ when ⟦ϕ⟧(x)+⟦ϕ′⟧(x) = 0. Using Lemma 2.4.2, this holds if and only if ⟦ϕ⟧ = 0 and ⟦ϕ′⟧ = 0, and thus if and only if x ⊨ϕ ∧x ⊨ϕ′.

4. x ⊨ϕ ∨ϕ′ when ⟦ϕ⟧ ∗ ⟦ϕ′⟧ = 0. This holds and only if ⟦ϕ⟧ = 0 or ⟦ϕ′⟧ = 0.

5. As for ∧, the sum ∑x∈1..len(ς(C)) ⟦ϕ⟧ς is zero if and only if all of its component summands are zero.

6. The product ∏x∈1..len(ς(C)) ⟦ϕ⟧ς is zero if and only if one of its component summands is zero.

7. By Figure 2, ⟦t < Ci⟧ς means precisely that t is strictly less than every entry in the ith row of ς(C). Similarly for Ci < t. We will also use t ≤ Ci and Ci ≤t as per Notation 2.2.7. Because ς(C) is an integer matrix, ⟦t ≤ Ci⟧ς means precisely that t is less than or equal to every entry in the ith row of ς(C), and similarly for Ci ≤t.End of proof

Remark 2.4.5

Theorem 2.4.4 is important — a logical judgement is valid precisely when its polynomial translation is — but mathematically it is elementary. It just dresses up the fact that in ℚ,

• a sum of two nonnegative numbers is zero if and only if both numbers are zero, and

• a product of two nonnegative numbers is zero if and only if at least one of the numbers is zero.

But of course, this is just what we need to precisely interpret logical conjunction / universal quantification, and logical disjunction / existential quantification, respectively.

What is absent from Theorem 2.4.4, because it is absent from our syntax in Figure 1, is negation — there is no explicit predicate-former ¬ϕ. This is because it can be expressed using the rest of the logic; we will see later in Notation 4.2.6 and Theorem 4.2.7 that our logic is complemented. That is: given ϕ, we can write a complement predicate ∼ϕ that is valid if and only if ϕ is not valid.

But note also that our examples will show that even the negation-free fragment of FOL is very expressive (expressive enough to e.g. encode a Turing-complete model of computation; see Subsection 3.9).

For now, we just note that Theorem 2.4.4 is more powerful than it looks, and it will turn out that it can indeed lay claim to expressing full first-order logic with negation.

Remark 2.4.6 is in a sense a continuation of Remark 2.2.6:

Remark 2.4.6 (Dualities).

1. ∃ is a natural de Morgan dual to ∀ (as usual). We will use ∀ all the time in our practical examples below, but not make much use of ∃. It costs nothing to include it anyway.

2. reify maps from nonnegative polynomials to all polynomials just by being the identity. This is in a sense dual to the ‘comparison with zero’ (t = 0), which maps from all polynomials to nonnegative polynomials by squaring. We will use this, most notably in our complementation operation from Notation 4.2.6.

3 Expressing functions

3.1 Simpler is better

Remark 3.1.1

We have our logic and its denotation. We are now ready to use it to specify functions.

The format of the results in this section is generally consistent:

1. We specify some (well-known) mathematical function, such as exponentiation.

2. We write a predicate in our formal syntax from Definition 2.2.3(3). This will correspond in some fairly natural way to the specification.

3. We state a soundness lemma, whose proof is usually elementary from Theorem 2.4.4, that the semantics of the predicate as per Figure 2 accurately captures the specification.

This can be a bit fiddly, because concretely manipulating large-ish expressions by hand can be fiddly, but mathematically it is straightforward. There is supposed to be a close match between the mathematical intuition, the formal syntax, and the semantics, so that the soundness proofs become straightforward. Our framework is designed to impose a minimal overhead, above and beyond any complexities that may be inherent in what is being expressed.

So for example, if the reader

• looks at Definition 3.2.1 (mathematical definition of exponentiation), and then

• looks at Figure 3 (formal predicate in our logic), and finally perhaps

• looks at Example 3.2.11 (unpacking the polynomial to which the formal predicate compiles)

and finds that it all looks rather straightforward, then that simplicity is a feature, not a bug.

3.2 Expressing a power function (with worked examples)

We start with a simple example: how to express a power function (exponentiation) ab for a, b ∈ℕ≥0.

Definition 3.2.1

Recall the standard inductive definition of ab for a, b ∈ℕ≥0:

base case pow(a, 0) = 1inductive step pow(a, b+1) = a ∗pow(a, b)
Remark 3.2.2

The reader may know that this definition is not particularly efficient. In Remark 3.2.14 we mention the efficient definition; but for the purposes of an initial example, Definition 3.2.1 will serve us very well.

Note an elementary point that definitions like Definition 3.2.1 implicitly equate computation with derivation, because when we try to compute a value — pow(2, 2), say — we end up with a simple derivation-tree as follows:

base casepow(2, 0) = 1inductive steppow(2, 1) = 2inductive steppow(2, 2) = 4

This derivation-tree, simple as it is, illustrates the close link between logic and computation.

The schema in Definition 3.2.4 and Figure 3 is typical of how we will work, so we spell it out now:

Notation 3.2.3

1. For each function or relation of interest we assume a matrix variable symbol C.

2. For each matrix variable symbol C, we write out a validity predicate χC, corresponding to the function or relation which we wish to specify.

3. We say that an interpretation ς satisfies this validity predicate when ⊨ς χC.

Recall that the ⊨ς χC notation is from Definition 2.3.2(4); it means x ⊨ς χC and so ⟦χC⟧(x) = 0 for some x (the choice of which will not matter, because X will be quantified in χC, as we shall see).

Definition 3.2.4

Assume a matrix variable symbol pow with arity arity(pow) = 4. Thus, the interpretation ς(pow) is a 4 × n integer matrix, for n ≥ 1.19 We will encode an assertion that pow encodes a (partial) power function, such that:

1. Row 1 (the values of pow1(X)) stores input values a.

2. Row 2 (the values of pow2(X)) stores input values b.

3. Row 3 (the values of pow3(X)) stores output values ab.

4. Row 4 (the values of pow4(X)) stores a pointer (specifically: a column index) to a column in the pow matrix that represents the recursive call to pow in clause 2 of Definition 3.2.1 above.

In Figure 3 we

1. define syntactic sugar,

2. use it to express the clauses from Definition 3.2.1, and

3. write a validity predicate χpow, to express that pow encodes a partial power function.

Examples of matrices that do and do not satisfy the validity predicate χpow are in Examples 3.2.8 and 3.2.9.

pow1(t) sugars to in1(t) pow2(t) sugars to in2(t)pow3(t) sugars to out(t) pow4(t) sugars to rec(t)baseCase(X) = (in2(X) = 0) ∧(out(X) = 1) indStep(X) = in1(X) = in1(rec(X)) ∧ in2(X) = in2(rec(X))+1 ∧ out(X) = in1(X) ∗out(rec(X))χpow = 1 ≤rec ≤len(pow) ∧∀powX.(baseCase(X) ∨indStep(X))
Figure 3: Expressing a power function (exponentiation) ab (Definitions 3.2.1 and 3.2.4)
Definition 3.2.5

Suppose ln ∈ℕ≥1. Say that a 4 × ln matrix M encodes a partial power function when

∀x ∈1..ln. M(3, x) = M(1, x)M(2,x).

In words, M encodes a partial power function when for each column, the third entry of that column is equal to the first entry raised to the power of the second.

Lemma 3.2.6

Suppose ς is an interpretation (Definition 2.3.2(1)). Then

• if ⊨ς χpow

• then ς(pow) encodes a partial partial power function (Definition 3.2.5).

Proof

We examine the clauses in Figure 3 and using Theorem 2.4.4 we check that they correctly encode the definition in Definition 3.2.1.

We also need to check well-foundedness — that the pointers in the matrix do not point in a circle — but this follows from the treatment of the second input argument (named b in Definition 3.2.1). An overall discussion of this point is in Remark 3.9.8.End of proof

Remark 3.2.7

The significance of Lemma 3.2.6 is not that the power function can be interpolated. Any function f : ℕ →ℕ, however fast it goes to infinity, coincides with some polynomial on any given {1, . . . , ln}; just use the interpolating polynomial itplnt(f(1), . . . , f(ln)) from Definition 2.1.4. The significance of Lemma 3.2.6 is the predicate characterisation of valid computations of the power function, uniformly and independently of ς.

Example 3.2.8

We illustrate some matrices that pass the validity check ⊨ς χpow and so by Lemma 3.2.6 encode a partial power function:

2 2 20 1 21 2 41 1 2 and 2 2 22 1 04 2 12 3 3 and 2 2 2 20 2 1 01 4 2 12 3 1 1 and 3 2 3 20 0 1 11 1 3 21 1 1 2

Note how all of these matrices can be viewed as concrete implementations of the derivation-tree illustrated in Remark 3.2.2:

1. The leftmost matrix encodes the base case of a derivation that 22 = 4 in column 1, the second step in column 2, and the third and final step of the derivation in column 3. The fourth entry in columns 2 and 3 contain a number which is a pointer to the previous step/column in the derivation; the fourth entry in column 1 also contains a number, but it is not used.

2. The columns do not need to appear in any particular order, so long as the pointers match up; the next matrix illustrates this (by putting the columns in the reverse order).

3. Columns can also be duplicated; the third matrix illustrates this.

4. The fourth (rightmost) matrix includes information from two computations; that 21 = 2 and 31 = 3.

Example 3.2.9

The converse implication for Lemma 3.2.6 does not hold: it is possible for ς(pow) to encode a partial power function yet ¬(⊨ς χpow). Take for example

ς(pow) = 2 2 4 2

This one-column matrix encodes a partial power function because 22 = 4, but it fails the validity predicate because the entry in the fourth row does not point to a column showing that 21 = 2, so this fails the last line of indStep in Figure 3. We can think of it as corresponding to an incomplete derivation-tree:

????inductive steppow(2, 2) = 4

We consider another example:

ς(pow) = 2 2 22 1 04 2 12 3 0

This matrix encodes a partial power function because 22 = 4 and 21 = 2 and 20 = 1. Furthermore, the entry in the fourth row of the first column does point to a column showing that 21 = 2, that the fourth row of the second column does point to a column showing that 20 = 1. However, this fails the range check just for a technical reason: the entry in the fourth row of the third column is 0, which is not in the range 1 to 3.

Remark 3.2.10

In constructive logic, something is only deemed ‘true’ when we have a concrete witness for its truth [vD02].20

The way our encoding of logic works, as illustrated in Examples 3.2.8 and 3.2.9, feels constructive in this sense. It might help such a reader to think of matrices as follows: the matrices are used to encode deduplicated derivation-trees. Columns correspond to nodes, and we include index pointers to link these nodes together.

Example 3.2.11

We take a moment to unpack the concrete polynomial that Figure 3 expresses.

Assume we have some interpretation ς and write pow = ς(pow). Recall from Definition 2.3.2(1) that this is a 4 × n matrix for some n ≥ 1. Mirroring the sugar in Figure 3, we write:

in1 = itplnt(pow1) in2 = itplnt(pow2) out = itplnt(pow3) rec = itplnt(pow4)

Assume that every entry in pow4 is a valid index of a column in pow, so that pow passes the range check and

⟦0 < pow4 < len(pow) + 1⟧ς = 0

— meaning that this is ‘true’.

Then ⟦χpow⟧ς from Figure 3 expands as follows — where, as per Figure 2, ∧ maps to +, ∨ maps to ∗, ∀ maps to ∑, and t = t′ maps to (t −t′)2:

χpow = 1 ≤pow4 ≤len(pow) ∧ ∀powX.(baseCase(X) ∨indStep(X))
⟦χpow⟧ς = 0 + ∑1≤x≤n((in1(x)2 + (out(x)−1)2)∗((in1(x)−in1(rec(x)))2+ (in2(x)−(in2(rec(x))+1))2+ (out(x) −in1(x)∗out(rec(x)))2))

If this evaluates to zero, then pow really does encode a partial power function.21

Remark 3.2.12 (Analysis of polynomial degree).

We can make some comments on the degree of the polynomial in Example 3.2.11:

1. Range checks correspond to constant numbers (0 if true, 1 if false). This makes range checks ‘free’, in the sense that they contribute nothing to the degree of the polynomial.

2. ∧ and ∀ corresponds to +. This means that conjunction and universal quantification are ‘free’, in the sense that they do not increase the degree of a polynomial beyond the degrees of the components.

3. ∨ corresponds to ∗. This is linearly expensive, in the sense that the degree is the sum of the degrees of the components.

4. Polynomial instantiation, as triggered e.g. by the recursive call out(rec(x)) above, is multiplicatively expensive: it multiplies degrees of the polynomials involved. For example, if we set P(X) = X2 and Q(X) = X3 then P(Q)(X) = (X3)2 = X6.

5. The length of the matrix is linearly expensive in the degree of the interpolating polynomial: as per Definition 2.1.4(2), to interpolate a vector of length n requires a polynomial of degree at most n−1.

6. The implementation is optimised for simplicity, not efficiency. We will come to that shortly.

For brevity write n = len(pow); so this is the number of columns in pow and is (one plus) the degree of the interpolants in1, in2, out, and rec. Checking the polynomial, we see that its degree is O(n4), coming from the component (in1 ∗ out(rec))2 on the far right-hand side, and in particular from the polynomial instantiation out(rec). Now for pow as specified in Definition 3.2.1, n (the number of columns) is equal to b, so the degree order of this specification, by which we mean the degree of the polynomials it produces, is O(b4). We improve this bound in Remark 3.2.14.

Remark 3.2.13

Just because a polynomial has high degree does not necessarily make it complicated nor expensive to compute. For instance, X100 had degree 100, but 10100 is not particularly expensive to compute, and the polynomial has only one root up to multiplicities, so in the logical sense mentioned in Remark 2.3.6(6) it is equivalent to X2.22

Degree order as a complexity metric is its own thing.

Remark 3.2.14

Continuing Remark 3.2.12, we can also try to keep n small, which amounts to minimising the number of calls to pow. As is well-known, a more efficient specification of ab is this:

pow(a, 0) = 1 pow(a, 2 ∗b) = pow(a, b) ∗pow(a, b) pow(a, 2 ∗b + 1) = a ∗pow(a, b) ∗pow(a, b)

Logically, this leads to smaller derivations, and algorithmically it yields a runtime that is logarithmic in b rather than linear (parametrically over the complexity of our multiplication algorithm).

We could translate this into our logic as we did in Definition 3.2.4, and this would yield an implementation of degree order O(log(b)4). More on efficiency in Remark 3.4.6(2) and Subsection 6.2.

χsqrt = 0 ≤sqrt2 ∧ ∀sqrtX.sqrt2(X) ∗sqrt2(X) = sqrt1(X)
Figure 4: Expressing a positive square root function √a (Definitions 3.3.1 and 3.3.2)

3.3 Expressing a square root function

The square root √a is a simple example which nicely illustrates that validity predicates are assertions, not computations. In particular, we can verify that a matrix represents a partial square root function; just square the claimed root (see Definition 3.3.3). We do not have to design a square root algorithm ourselves. This is an elementary point, which may be familiar to readers familiar with succinct proofs, but we spell out the details:

Definition 3.3.1

Recall that for a ∈ℚ≥0, the (positive) square root function √a is specified by

(√a)2 = a ∧√a ≥0.
Definition 3.3.2

Assume a matrix variable symbol sqrt with arity arity(sqrt) = 2. In Figure 4 we use our logic to express a validity predicate χsqrt that sqrt encodes a partial positive square root function, such that:

1. Row 1 (values of sqrt1(X)) stores input values a.

2. Row 2 (values of sqrt2(X)) stores output values √a ≥ 0.

Definition 3.3.3

Suppose ln ∈ℕ≥1. Say that a 2 × ln matrix M encodes a partial positive square root function when

∀x ∈1..ln. (0 ≤M(2, x) ∧M(2, x)2 = M(1, x)).
Lemma 3.3.4

Suppose ς is an interpretation (Definition 2.3.2(1)). Then the following are equivalent:

1. ⊨ς χsqrt.

2. ς(sqrt) encodes a partial positive square root function, as per Definition 3.3.3.

Proof

We examine χsqrt in Figure 4 and see that it correctly encodes the definition in Definition 3.5.1.End of proof

Remark 3.3.5

There are no pointers involved in Lemma 3.3.4, so we get a logical equivalence. Contrast with Lemma 3.2.6 and Examples 3.2.8 and 3.2.9 for pow.

Remark 3.3.6

The point made by Definition 3.3.3, Figure 4, and Lemma 3.3.4 is not that positive square roots are particularly interesting.23 What matters is that actually computing √a is done by whoever provides ς (i.e. the ‘prover’). Intuitively, our logic is about verification. Thus, we assume a ς is provided, and we verify that it satisfies whatever validity predicates have been claimed of it.

3.4 Expressing Fibonacci

The Fibonacci function is a classic example in a certain kind of undergraduate course. We consider it in our system. It is a simple example, though nontrivial, and as we discuss in Remark 3.4.6 it raises some useful points:

fib1(t) sugars to in(t) fib2(t) sugars to out(t)fib3(t) sugars to rec1(t) fib4(t) sugars to rec2(t)baseCase0(X) = (in(X) = 0) ∧(out(X) = 1)baseCase1(X) = (in(X) = 1) ∧(out(X) = 1)indStep(X) = in(X) = in(rec1(X)) + 2 ∧in(rec2(X)) = in(rec1(X)) + 1 ∧out(X) = out(rec1(X)) + out(rec2(X))χfib = 1 ≤rec1 ≤len(fib) ∧1 ≤rec2 ≤len(fib) ∧ ∀fibX.(baseCase0(X) ∨baseCase1(X) ∨indStep(X))
Figure 5: Expressing the Fibonacci function fib(a) (Definitions 3.4.1 and 3.4.4)
Definition 3.4.1

Recall that the Fibonacci sequence fib(a) for a ∈ℕ≥0 is defined by:

base case 0 fib(0) = 0 base case 1 fib(1) = 1

inductive step fib(a + 2) = fib(a) + fib(a+1)
Definition 3.4.2

Assume a matrix variable symbol fib with arity arity(fib) = 3. We can think of this as a three-row matrix.

We will use our logic to express a validity predicate χfib that fib encodes the Fibonacci function, such that:

1. Row 1 (values of fib1(X)) stores input values a.

2. Row 2 (values of fib2(X)) stores output values fib(a).

3. Row 3 (values of fib3(X)) stores an index of a column in fib, corresponding to the first recursive call to fib in clause 3 of Definition 3.4.1.

4. Row 4 (values of fib3(X)) stores an index of a column in fib, corresponding to the second recursive call to fib in clause 3 of Definition 3.4.1.

Definition 3.4.3

Suppose ln ∈ℕ≥1. Say that a 4 × ln matrix M encodes a partial Fibonacci function when

∀x ∈1..ln. M(2, x) = fib(M(1, x)).
Definition 3.4.4

In Figure 5 we

1. define syntactic sugar,

2. use it to express the clauses from Definition 3.4.1, and

3. write a validity predicate χfib to express that fib encodes a partial Fibonacci function.

Lemma 3.4.5

Suppose ς is an interpretation (Definition 2.3.2(1)). Then

1. if ⊨ς χfib,

2. then ς(fib) encodes a partial Fibonacci function, as per Definition 3.4.3.

Proof

We examine the clauses in Figure 5 and see that they correctly encode the definition in Definition 3.4.1. The range checks 1 ≤ fib3 ≤ len(fib) and 1 ≤ fib4 ≤ len(fib) are there to exclude out-of-bounds pointer errors.End of proof

Remark 3.4.6

There are a few interesting observations to make about Definition 3.4.1 and Figure 5.

1. It is not the case that ς(fib) has to contain the entries of the Fibonacci sequence in order. Each column has to contain a value a, the number fib(a), and (if a ∉{0, 1}) it contains pointers to two columns representing ‘recursive calls’. Where those recursive calls are located inside ς(fib) does not really matter.

2. We put ‘recursive calls’ in scare quotes because these are not recursive calls to a computation.24 Definition 3.4.1 is famous in undergraduate courses because, if translated directly to code, it is very inefficient; each call to fib creates two sub-calls, thus giving the program exponential complexity. A standard solution is to memoise the computation; store the results of previous calls and replace them with lookups if the function is called again on the same input. Figure 5 is already naturally memoised. Indeed, it is nothing more than a lookup-table. As we noted in Remark 3.3.6, our logic is verifying (not computing!) a ς.25 So the complexity of the program implicit in Definition 3.4.1 is actually linear (not exponential), because our semantics is in some sense inherently memoised.

Remark 3.4.7 (Fast Fibonacci and algebraic extensions of ℚ).

Optimised methods for computing Fibonacci numbers exist. See for instance a well-written online overview [Nay23] and an algorithmic treatment [Cap20] which uses the Binet formula — a paper on this topic exists [Das18], however, the webpage includes significant additional optimisations.

This is interesting because The Binet formula uses √5, which is irrational and so is not in ℚ, which is the field we use in this paper. So what this example illustrates is that ℚ may not be enough: we may wish to talk about roots of polynomials that are not rationals, such as x2 = 5, and if so, we might need to consider algebraic extensions, such as ℚ(√5). Technically, this should not be a problem.

3.5 Expressing Ackermann’s function

Ackermann’s function is another classic example. We check how it comes out in our framework:

Definition 3.5.1

Recall Ackermann’s function Ack(a, b) for a, b ∈ℕ≥0, defined by:

base case Ack(0, b) = b + 1inductive step 0 Ack(a + 1, 0) = Ack(a, 1)inductive step 1 Ack(a + 1, b + 1) = Ack(a, Ack(a + 1, b))
Definition 3.5.2

Assume a matrix variable symbol Ack with arity arity(Ack) = 5. We can think of this as a five-row matrix.

We will use our logic to express a validity predicate χAck that Ack encodes a (partial) Ackermann function, such that:

1. Row 1 (values of Ack1(X)) stores input values a.

2. Row 2 (values of Ack2(X)) stores input values b.

3. Row 3 (values of Ack3(X)) stores output values Ack(a, b).

4. Row 4 (values of Ack4(X)) stores an index of a column in the Ack matrix, corresponding to the first recursive call to Ack in clauses 2 and 3 of Definition 3.5.1.

5. Row 5 (the values of Ack5(X)) stores an index of another column in the Ack matrix, corresponding to the second recursive call to Ack in clause 3 of Definition 3.5.1.

Definition 3.5.3

Suppose ln ∈ℕ≥1. Say that a 5 × ln matrix M encodes a partial Ackermann’s function when

∀x ∈1..ln.M(3, x) = Ack(M(1, x), M(2, x)).
Definition 3.5.4

In Figure 6 we

1. define syntactic sugar,

2. use it to express the clauses from Definition 3.5.1, and

3. write a validity predicate χAck to express that Ack encodes a partial Ackermann function.

Ack1(t) sugars to in1(t) Ack2(t) sugars to in2(t)Ack3(t) sugars to out(t) Ack4(t) sugars to rec1(t)Ack5(t) sugars to rec2(t) baseCase(X) = (in1(X) = 0) ∧(out(X) = in2(X) + 1)indStep0(X) = in1(X) = in1(rec1(X)) + 1 ∧ in2(X) = 0 ∧out(X) = out(rec1(X))indStep1(X) = in1(X) = in1(rec2(X)) + 1 ∧ in2(X) = in2(rec1(X)) + 1 ∧ out(X) = out(rec2(X)) ∧ in1(rec1(X)) = in1(rec2(X)) + 1 ∧ in2(rec2(X)) = out(rec1(X))χAck = 1 ≤rec1 ≤len(Ack) ∧1 ≤rec2 ≤len(Ack) ∧ ∀AckX.(baseCase(X) ∨indStep0(X) ∨indStep1(X))
Figure 6: Expressing Ackermann’s function Ack(a, b) (Definitions 3.5.1 and 3.5.4)
Lemma 3.5.5

Suppose ς is an interpretation (Definition 2.3.2(1)). Then

1. if ⊨ς χAck

2. then ς(Ack) encodes a partial Ackermann function, as per Definition 3.5.3.

Proof

We examine the three clauses in Figure 6 and see that they correctly encode the definition in Definition 3.5.1. The range checks 1 ≤ Ack4 ≤ len(Ack) and 1 ≤ Ack5 ≤ len(Ack) are there to exclude out-of-bounds pointer errors.End of proof

3.6 Bitwise representation

Unsigned 64-bit integers — the familiar uint64 datatype — are a standard datatype of practical interest in computing. Bitwise integers are the native notion of number in many programming languages.26 For example, C uses 64-bit or 32-bit integers, and Ethereum uses 256-bit integers. It is straightforward to represent them:

Definition 3.6.1

We express that t is equal to zero or one (i.e. that t represents a single bit of binary data) using a little syntactic sugar:

isBinary(t) is sugar for t = 0 ∨t = 1.

Unpacking Figure 2, isBinary(t) corresponds to a polynomial t2 ∗ (t − 1)2.

Definition 3.6.2

Assume a matrix variable symbol uint64 with arity(uint64) = 65, which we can think of as representing a 65-row matrix.

1. Row 1 should store a whole number 0 ≤n < 264, and

2. rows 2 to 65 should store its binary expansion (with smallest bit first). Validity of uint64 is simply

χuint64 = ∀uint64X.(uint641(X) = ∑i∈0..63 2i ∗uint64i+2(X) ∧ isBinary(uint642(X)) ∧. . . ∧isBinary(uint6465(X)))

This just asserts that for each column in uint64, elements 2 to 65 of that vector do indeed store bits representing the binary representation of element 1.

Lemma 3.6.3

Suppose ς is an interpretation (Definition 2.3.2(1)). Then the following are equivalent:

1. ⊨ς χuint64 for χuint64 as defined in Definition 3.6.2.

2. ς(uint64) encodes a list of bitwise expansions, by which we mean precisely that

∀1 ≤x ≤len(ς(uint64)). ς(uint64)1(x) =∑i∈0..632i ∗ς(uint64)i+2(x).
Proof

We examine χuint64 in Definition 3.6.2 and using Theorem 2.4.4 and basic arithmetic see that this is precisely what it encodes. Note that there are no range checks, pointers, or recursive calls involved; this is just straightforward arithmetic. Note also that 2i is in the predicate above is just a number (not a power of X), so has degree zero in X.End of proof

Remark 3.6.4

We get a decimal representation just by generalising isBinary to isDecimal:

isDecimal(t) is sugar for t = 0 ∨t = 1 ∨. . . ∨t = 9.

and use a matrix variable symbol uint64base 10 with validity predicate

clause(X) =(uint64base 10 1(X) = ∑i∈0..63 10i ∗uint64base 10 i+2(X) ∧isDecimal(uint64base 10 2(X)) ∧. . . ∧isDecimal(uint64base 10 65(X))).

We can also nest representations and for example represent a number in the range 0 to (264)64 by taking its 64-digit expansion base 264.

3.7 Range check

Remark 3.7.1

The clause for the range check < in Figure 2 is simple — just check that the relevant row in the matrix satisfies the required bound, and return 0 if it is satisfied and 1 if it is not.

This in itself does not increase expressivity: the range check can be compiled down to the language without < (at some cost); see Remark 5.1.3(4). It could also be computed direct on silicon, as we note in Subsection 5.2.27

In particular, we see from our examples — such as those in Figures 3 and 6 — that we typically want to prove range checks that have an upper and lower bound, having this form:

1 ≤Ci ≤len(C).

We can translate predicates of this form into ones that do not mention <, as follows:

Definition 3.7.2

Suppose l, r ∈ℤ and l ≤r. Then define a predicate rangel,r(X) by

rangel,r(X) = (X = l) ∨(X = l+1) ∨. . . ∨(X = r−1) ∨(X = r).
Remark 3.7.3

Range checks are special cases of set membership assertions. Succinct (and zero knowledge) set membership schemes are a field of research in their own right ([BCF+23] contains a recent survey). So: the schema in Definition 3.7.2 may not be optimal and in a practical implementation of these ideas we might wish to improve it further, but for proof-of-concept Definition 3.7.2 will serve our purposes, and it is simple. Lemma 3.7.4 says that it does what we need it to do:

Lemma 3.7.4

Suppose ς is an interpretation. Then the following are equivalent:

1. ⊨ς 1 ≤ Ci ≤ len(C).

2. ⊨ς ∀XC.range1,len(C)(Ci(X)).

Proof

ς(C) is by Definition 2.3.2(1) an integer matrix, and the polynomial ⟦rangel,r⟧ by construction in Definition 3.7.2 and Figure 2 has zeroes precisely at the integers between l and r inclusive, which by Notation 2.2.7 and Figure 2 is precisely what 1 ≤ Ci ≤ len(C) checks.End of proof

Remark 3.7.5

If ς(C) is a very long matrix then ⟦range1,len(C)(Ci(X))⟧ might be a large (high-degree) polynomial. But, in the context of the succinct proofs (see discussion in Subsection 5.1) this may be is a worthwhile trade-off.

Remark 3.7.6

We can also exploit uint64 from Subsection 3.6 to do a simple range check. Assume a matrix variable symbol range64 with arity(range64) = 2, and with validity condition

clause(X) = 1 ≤ range642 ≤ len(uint64) ∧(range641(X) = uint641(range642(X))).

Intuitively, we can think of the above as follows:

1. range641(X) stores some number n.

2. range642(X) stores a pointer to a proof in uint64 that n has a 64-bit representation.

3. The pointers in range642 must be in-bound for the addressable range of uint64; i.e. they must be numbers between 1 and len(uint64).

The above can only happen if 0 ≤n < 264, so this all amounts to doing range checks.

3.8 Iteration

Definition 3.8.1

Recall that if f : ℤ →ℤ is a function and a ∈ℕ≥0, then the a-fold iteration iterf(a) : ℤ →ℤ of f is the function that inputs b ∈ℤ and returns (a times f ◦· · · ◦f)(b).

This can be defined by:

base case iterf(0)(b) = binductive step iterf(a + 1)(b) = f(iterf(a)(b))
Definition 3.8.2

Assume a matrix variable symbol f, with arity arity(f) = 3, along with a validity predicate χf which expresses that f3(X) = f(f1(X), f2(X)). We can think of this intuitively as a matrix of columns all having the form (a, b, f(a, b)), for various values of a and b.

There is no obstacle to having more rows, as we did for instance in Figure 6; we take three just for simplicity.

We now assume a binary propositional constant iterf with arity arity(iterf) = 5. In Figure 7 we use our logic to express that iterf encodes an a-fold iteration of f on an input value b, such that:

1. Row 1 (values of iterf,1(X)) stores the number of iterations a.

2. Row 2 (values of iterf,2(X)) stores input values b.

3. Row 3 (values of iterf,3(X)) stores output values iterf(a)(b).

4. Row 4 (values of iterf,4(X)) stores pointers to recursive calls to iterf, as required in clause 2 of Definition 3.8.1 above.

5. Row 5 (values of iterf(5, X)) stores pointers to calls to f, corresponding to the call to f in clause 2 of Definition 3.8.1 above.

Definition 3.8.3

Suppose f : ℤ →ℤ is a unary function and suppose ln ∈ℕ≥1. Say that a 5 × ln matrix M encodes a partial iteration of f when

∀x ∈1..ln. M(3, x) = f M(1,x)(M(2, x)).
iterf,1(t) sugars to in1(t) iterf,2(t) sugars to in2(t)iterf,3(t) sugars to out(t) iterf,4(t) sugars to rec(t)iterf,5(t) sugars to callf(t) baseCase(X) = (in1(X) = 0) ∧(out(X) = in2(X))indStep(X) = in1(X) = in1(rec(X)) + 1 ∧ in2(X) = in2(rec(X)) ∧ out(X) = f2(callf(X)) ∧ f1(callf(X)) = out(rec(X))χiterf = 1 ≤rec ≤len(iter) ∧1 ≤callf ≤len(f) ∧ ∀iterf X.(baseCase(X) ∨indStep(X))
Figure 7: Expressing iterf(a)(b); a-fold application of f to b (Definitions 3.8.1 and 3.8.2)
Lemma 3.8.4

Suppose ς is an interpretation (Definition 2.3.2(1)). Then

1. if ⊨ς iterfValid

2. then ς(iterf) encodes a partial iteration of f, as per Definition 3.8.3.

Proof

We examine the clauses in Figure 7 and using Theorem 2.4.4 see that they do indeed encode the definition in Definition 3.8.1. The bound checks 1≤ iter4 ≤ len(iter) and 1≤ iter5 ≤ len(f) exclude out-of-bounds pointer errors.End of proof

Remark 3.8.5

We see no inherent barrier to mutual inductive definitions. We just declare several matrix variable symbols and engineer pointers between them for the (mutual) inductive calls. It may be necessary to add a counter to prevent looping; see Subsection 3.9.

3.9 SK combinators

Remark 3.9.1

The SK combinator system forms a Turing-complete model of computation; see [Bim20, KvOvR93] or [Bar84, Chapter 7]).28 Combinators are also a quite common compile target for modern high-level programming languages.29 So to specify combinators is interesting in itself, and also it shows how our logic can specify the valid execution traces of a realistic and relevant combinatory virtual machine.

Definition 3.9.2

1. Combinator expressions are a formal syntax defined by:

t ::= S | K | tt.

So a combinator is either an S, a K, or an application of a combinator term to a combinator term.

2. An evaluation relation for combinators is as follows:

(Kred)(Ks)t∗→s(Sred)((Ss)t)u∗→(st)(su)(Id)t∗→ts∗→s′t∗→t′(Par)st∗→s′t′s∗→t t∗→u(Tran)s∗→u

The ‘red’ in (Kred) and (Sred) stands for ‘reduce’; intuitively these represent a single computation step. (Id) is the identity (no computation); (Par) is parallel computation; and (Tran) (for transitivity) chains computations sequentially. The relation ∗→ is intuitively a multistep computation relation. When t∗→t′ holds, we may say that t′ is a (possibly trivial) reduct of t.

Example 3.9.3

We give a very simple example of a ∗→ derivation, which is valid for t any combinator term:

(Id)t∗→t(Kred)(Kt)(Kt)∗→t(Sred)(SKKt)∗→t

This example shows that SKK behaves as an identity element, i.e. it codes the identity function that inputs a value t and outputs that same value t.

The computation above is simple, of course, but it is nontrivial, and using (Par) and (Tran) we can parallelise and chain this and other computations. Larger examples include Boolean logic, arithmetic, and fixpoint operators (like the famous Y combinator). So the example above, while small, is canonical.

We now consider how to encode ∗→ in our logic. We use a trick to make our encoding more compact:

Definition 3.9.4

1. The Cantor pairing function is a well-known way of bijecting ℕ≥0 × ℕ≥0 with ℕ≥0. It has the characteristic that it can be expressed as a polynomial over ℚ (indeed, this is the only quadratic polynomial pairing function) [Nat16]:30

⟨x, y⟩′ = (x + y) ∗(x + y + 1) 2+ x = x2 + 3 ∗x + 2 ∗x ∗y + y + y22. (1)

2. The pairing function ⟨x, y⟩′ above is not quite what we need, because we want to reserve 0 to represent the combinator S and 1 to represent the combinator K. Accordingly, we adjust it with a two-element offset:

⟨x, y⟩= ⟨x, y⟩′ + 2.

3. We then define a Gödel encoding31 from the syntax of combinator expressions (Definition 3.9.2(1)) to ℕ, which is an injection defined by:

gdl(S) = 0 gdl(K) = 1 gdl(tt′) = ⟨gdl(t), gdl(t′)⟩.

It is routine to prove that this injection is actually a bijection between combinator expressions and the nonnegative natural numbers ℕ≥0.

Remark 3.9.5

In Equation (1) in Definition 3.9.4, we divide by 2. If we want a polynomial with coefficients over ℤ we could just as well use ⟨x, y⟩′ ∗ 2, and retain integer coefficients throughout. We would lose bijectivity of the pairing function, but in the context of this prototype that would be fine too.

Definition 3.9.6

Assume a matrix variable symbol evl with arity arity(evl) = 8, which we can think of as storing an 8-row matrix. In Figure 8, we

1. define syntactic sugar,

2. use it to express the clauses from Definition 3.9.2, and

3. write a validity predicate χSK to express that evl encodes a partial combinator reduction relation.

0 sugars to S 1 sugars to Kevl1(t) sugars to lhs(t) evl2(t) sugars to rhs(t)evl3(t) sugars to s(t) evl4(t) sugars to t(t)evl5(t) sugars to u(t) evl6(t) sugars to rec1(t) evl7(t) sugars to rec2(t)evl8(t) sugars to count(t) Kred(X) = lhs(X) = ⟨⟨K, rhs(X)⟩, t(X)⟩Sred(X) = lhs(X) = ⟨⟨⟨S, s(X)⟩, t(X)⟩, u(X)⟩∧ rhs(X) = ⟨⟨s(X), t(X)⟩, ⟨s(X), u(X)⟩⟩Id(X) = lhs(X) = rhs(X)Par(X) = lhs(X) = ⟨lhs(rec1(X)), lhs(rec2(X))⟩∧ rhs(X) = ⟨rhs(rec1(X)), rhs(rec2(X))⟩∧ count(X) = count(rec1(X))+1 ∧count(X) = count(rec2(X))+1Tran(X) = lhs(X) = lhs(rec1(X)) ∧rhs(X) = rhs(rec2(X)) ∧rhs(rec1(X)) = lhs(rec2(X)) ∧ count(X) = count(rec1(X))+1 ∧ count(X) = count(rec2(X))+1χSK = 1 ≤rec1 ≤len(evl) ∧ 1 ≤rec2 ≤len(evl) ∧ ∀evlX.(Kred(X) ∨Sred(X) ∨ Id(X) ∨Par(X) ∨Tran(X))
Figure 8: Expressing evaluation of combinator expressions (Definitions 3.9.2 and 3.9.6)
Remark 3.9.7

We read through the rows in evl one by one:

1. Row 1 represents the left-hand (unreduced) term.

2. Row 2 represents the right-hand (reduced) term.

3. Row 3 represents a subterm s of the term on the left-hand side.

4. Row 4 represents a subterm t of the term on the left-hand side.

5. Row 5 represents a subterm u of the term on the left-hand side (see rule (Sred)).

6. Rows 6 and 7 represent pointers to proof-obligations above the line (= inductive function-calls), as required in (Par) and (Tran).

7. Row 8 represents an abstract inductive quantity which increments with each derivation step. This prevents a derivation with cycles, and thus ensures that the underlying derivation is acyclic.32

Remark 3.9.8

Remark 3.9.7(7) describes an abstract counter to ensure acyclicity of the derivation trees represented by the matrices. The reader might wonder why we did not provision a similar abstract inductive quantity to avoid cycles in our matrices for exponentiation, Fibonacci, Ackermann’s function, or iteration. Iteration already has a counter inherent to its design, to count the number of times to apply the function. Exponentiation, Fibonacci, and Ackermann’s are inherently inductive on their numerical inputs; an explicit count entry would be harmless, but for those functions it would be redundant. Combinators are a structurally more complex definition and we need an explicit measure of derivation depth.

Definition 3.9.9

Suppose ln ∈ℕ≥1. Say that an 8×ln matrix M encodes a multistep combinator reduction relation when

∀x ∈1..ln. gdl-1(M(1, x))∗→gdl-1(M(2, x)).

Above, the ∗→ relation is defined in Definition 3.9.2. The gdl function bijects combinator expressions with nonnegative natural numbers (Definition 3.9.4(3)).

Lemma 3.9.10

Suppose ς is an interpretation (Definition 2.3.2(1)). Then

1. if ⊨ς χSK,

2. then ς(evl) encodes a partial combinator reduction relation, as per Definition 3.9.9.

Proof

We examine the clauses in Figure 8 and using Theorem 2.4.4 see that they do indeed encode the definition in Definition 3.9.2. This is a little bit fiddly because of the Gödel encoding of the combinator syntax, and the fact that there are four derivation rules, and one of them has three subderivations, so it is a challenge to not make a typo or miss out a bit of a rule — but conceptually this is a straightforward translation from one logical syntax into another.End of proof

Remark 3.9.11

We use the Cantor pairing function to build a simple Gödel encoding that packs a combinator term into a single number. We might prefer instead to store a combinator term as a list or as a tree of symbols. This is possible: it would add complexity to the representation above and thus to its validity predicate, but would not change the fundamental nature of what we are doing.

4 From range check to general recursion

4.1 Simple functions obtainable directly from the range check

Remark 4.1.1

A curious feature of our syntax in Figure 1 is the range check predicate <.

Our logic does not have a ‘runtime’ and a ‘compile time’ as such, but < has the flavour of a static ‘compile time’ check, in the sense that (for example) given ς, ⟦t < Ci⟧ς computes a number rather than a polynomial in X.33

In the examples above, we use range check to check for out-of-bounds pointer errors (see Examples 3.2.8 and 3.2.9 for concrete examples). But what is the range check really doing, and what is its full power? In this section we will examine this operator in more detail. We start by using the range check to specify some simple predicates and functions:

4.1.1 Strictly positive numbers pos

Definition 4.1.2 (Strictly positive numbers).

Assume a matrix variable symbol pos with

arity(pos) = 1 and validity predicate χpos(X) = (0 < pos1).

Lemma 4.1.3

Suppose ς is an interpretation. Then the following are equivalent:

1. ⊨ς χpos.

2. ς(pos) is a 1-row matrix (i.e. a vector) of strictly positive integers in ℕ>0.

Proof

This is exactly what the clause for range check in Figure 2 expresses, for 0 < pos1.End of proof

Remark 4.1.4

We introduce a strict inequality < rather than an inequality ≤ in Figure 1 so that we can express being strictly positive pos. If we took ≤ as primitive, it would be harder to express pos. This is because our logic does not include negation as primitive, so we cannot just express pos from a combination of ≤ and ≠.

4.1.2 The sign function sign and its corollary functions

Definition 4.1.5

We define functions

sign : ℚ →{−1, 0, 1} ⊆ℚ isZero : ℚ →{0, 1} neg : ℚ →{0, 1} neq : (ℚ × ℚ) →{0, 1} leq : (ℚ × ℚ) →{0, 1}

such that for a, b ∈ℚ:

sign(a) = 0 if a = 01 if a > 0−1 if a < 0isZero(a) ={ 0 if a = 01 if a ≠ 0neg(a) ={ 1 if a = 00 if a ≠ 0neq(a, b) ={ 0 if a ≠ b1 if a = bleq(a, b) ={ 0 if a ≤b1 if a ≰b
Remark 4.1.6

sign is the fundamental entity in Definition 4.1.5, and isZero, neg, neq, and leq follow from it, in the sense that we can derive everything using polynomial expressions using sign:

isZero(a) = sign(a)2neg(a) = 1 −isZero(a) = 1 −sign(a)2neq(a, b) = neg(a −b) = 1 −(sign(a −b))2leq(a, b) = sign(a −b) ∗(sign(a −b) −1)/2

We can use pos from Definition 4.1.2 to express sign, isZero, neg, neq, and leq from Definition 4.1.5:

Definition 4.1.7

Assume matrix variable symbols sign, isZero, and neg such that

arity(sign) = arity(isZero) = arity(neg) = 3.

1. Sugar sign1(X) to sign.in(X). This stores an input value a.

2. Sugar sign2(X) to sign.out(X). This stores the corresponding output value sign(a).

3. Sugar sign3(X) to sign.ptr(X). This stores a pointer to a column in pos1 (Definition 4.1.2) holding the absolute value of a.

We use similar sugar for isZero and neg. The validity predicates for sign, isZero and neg (using pos) are:

χsign(X) = 1 ≤sign.ptr ≤len(pos) ∧ ∀signX.((sign.in(X) = 0 ∧sign.out(X) = 0) ∨ (sign.in(X) = pos1(sign.ptr(X)) ∧sign.out(X) = 1) ∨ (((−1) ∗sign.in(X)) = pos1(sign.ptr(X)) ∧sign.out(X) = −1))χisZero(X) = 1 ≤isZero.ptr ≤len(pos) ∧ ∀isZeroX.((isZero.in(X) = 0 ∧isZero.out(X) = 0) ∨ (isZero.in(X)2 = pos1(isZero.ptr(X)) ∧isZero.out(X) = 1))χneg(X) = 1 ≤neg.ptr ≤len(pos) ∧ ∀negX.((neg.in(X) = 0 ∧neg.out(X) = 1) ∨ (neg.in(X)2 = pos1(neg.ptr(X)) ∧neg.out(X) = 0))

Assume matrix variable symbols neq, and leq such that

arity(neq) = arity(leq) = 4.

1. Sugar neq1(X) to neq.in1(X). This stores an input value a.

2. Sugar neq2(X) to neq.in2(X). This stores an input value b.

3. Sugar neq3(X) to neq.out(X). This stores the corresponding output value neq(a, b).

4. Sugar neq4(X) to neq.ptr(X). This stores a pointer to a column in pos1 (Definition 4.1.2).

We use similar sugar for leq. The validity predicates for neq and leq (using pos) are:

χneq(X) = 1 ≤neq.ptr ≤len(pos) ∧ ∀neqX.(((neq.in1(X)−neq.in2(X)) = 0 ∧neq.out(X) = 1) ∨ ((neq.in1(X)−neq.in2(X))2 = pos1(neq.ptr(X))∧ neq.out(X) = 0))χleq(X) = 1 ≤leq.ptr ≤len(pos) ∧ ∀leqX.(((leq.a(X)−leq.b(X)) = 0 ∧leq.out(X) = 0) ∨ ((leq.b(X)−leq.a(X)) = pos1(leq.ptr(X)) ∧leq.out(X) = 0)∨ ((leq.a(X)−leq.b(X)) = pos1(leq.ptr(X)) ∧leq.out(X) = 1))
Lemma 4.1.8

Suppose f ∈{sign, isZero, neg, neq, leq} is one of the functions from Definition 4.1.5. Then the corresponding validity predicate χf from Definition 4.1.7 correctly encodes f, in the sense that

• for each corresponding f ∈{sign, isZero, neg, neq, leq} and for every interpretation ς,

• if ⊨ς χpos (Definition 4.1.2) and ⊨ς χf then

• for every x ∈ 1..len(ς(f)) we have

ς(sign)(2, x) = sign(ς(sign)(1, x)) ς(isZero)(2, x) = isZero(ς(isZero(1, x))) ς(neg)(2, x) = neg(ς(neg)(1, x)) ς(neq)(3, x) = neq(ς(neq)(1, x), ς(neq)(2, x)) ς(leq)(3, x) = leq(ς(leq)(1, x), ς(leq)(2, x))
Proof

The functions in Definition 4.1.5 are simple enough, and so are the validity predicates in Definition 4.1.7. We check the correspondence and use Theorem 2.4.4.End of proof

Remark 4.1.9

1. There is some apparent overlap between isZero from Definition 4.1.5 and the ‘is equal to zero’ function λx.⟦X = 0⟧(x) = λx.x2 which we can build from the syntax and denotation in Figures 1 and 2.

But these are different functions: with isZero, the output is either 0 or 1, whereas with λx.x2 the output may be any nonnegative value. For example:

isZero(2) = 1 whereas ⟦2 = 0⟧ = 4,

as per Figure 2. Knowing that the output is precisely equal to 0 or 1 is a stronger property, and it matters because (for example) we can then easily get the ‘negation’ predicate (mapping 0 to 1 and any nonzero value to 0) as 1 − isZero(a). We cannot do this with λx.⟦X = 0⟧(x) = λx.x2.

2. neg is short for negation. It maps 0 (corresponding to ‘truth’) to 1, and any nonzero value (corresponding to ‘false’) to 0. This is a negation, and we have:

(a) We have excluded middle, since a ∗ neg(a) = 0 for every a ∈ℚ.34

(b) a + neg(a) ≠ 0 for every a ∈ℚ. This equals a if a ≠ 0, and equals 1 if a = 0.35

(c) Double negation neg(neg(a)) maps 0 to 0 and any nonzero element to 1. If we think of a truth-value a ∈ℚ≥0 as being either 0 or a nonzero ‘error value’, then neg(neg(a)) throws away the precise error value and just retains the information whether a was true or false. neg is not unique with the properties above; e.g. neg′ mapping a to 2 ∗ neg(a) has similar properties. This is as expected and it just reflects that there are many false (= nonzero) values.

4.1.3 Back from pos to the range check

Remark 4.1.10 (From pos back to <).

We saw above how, in the presence of the rest of the logic, the range checks t< Ci and Ci < t can express predicates for strictly positive numbers (Definition 4.1.2), and a sign function (Definition 4.1.7).

We take a moment to note that we can also go in the other direction, from pos to range checks. Let us for this Remark take a pos predicate as primitive in our syntax.

We can express the range check

t < Cias ∀CX.pos(Ci(X) −t),

and

t > Cias ∀CX.pos(t −Ci(X)).

Thus in some sense, <, pos, and also sign are all doing the same thing.

Remark 4.1.11

Continuing Remark 4.1.10, < is also clearly different from pos and sign, because t< Ci is variable-free and so has the flavour of a static check on the interpretation ς, whereas pos(x) and sign(x) have the flavour of being predicates.

Yet, in the context of the rest of the system they have the same expressivity. What deeper structure is being manifested here?

We propose that at a deeper level, what these constructs do is introduce the power of a knowledge modality. This is a modal operator that internalises some notion of necessitation, truth, knowledge, or provability inside the logic itself [Ver24] — that something is not just true or false, but also known to be such, proved to be such, or necessarily such, etc.

A feature of the notion of ‘false’ in our logic is that it is modelled by being nonzero, and there are infinitely many nonzero numbers so we cannot explicitly enumerate over all the possible ways of being false within our logic.36 What is significant about <, pos, and sign is not so much what they detect (though this is of course relevant); what really matters is that they map the truth or falsity of what they measure, to a finite set of values ({0, 1} or {0, 1, −1}), and this is where the effect of a knowledge modality comes from.

What makes < special, and better to use as a primitive than pos and sign, is that it still has a polynomial semantics — because (as we mentioned in Remark 4.1.1) ⟦t < Ci⟧ς returns a number, which is a polynomial. More on this in future work.

4.2 Arbitrary functions in terms and complementation in predicates

Remark 4.2.1

The term language in Figure 1 does not accommodate arbitrary functions f : ℚn → ℚ. This is by design, since Figure 2 presents a polynomial semantics. But it would be nice if we could have our cake and eat it too: use arbitrary functions in our terms, and still get the goodness of polynomial expressions.

This is impossible in the general case, but we do not need the general case: a simple polynomial interpolation is sufficient. So, we will use a matrix variable symbol f, with a validity predicate that expresses that f interpolates the desired function f.

Similarly, the predicate language in Figure 1 does not have a negation ¬ϕ. We can easily (in retrospect) interpret truth as zero and falsity as non-zero and ∧ as + and ∨ as ∗, because 0, +, and ∗ are naturally polynomial. Negation is different: no low-degree polynomial maps 0 to a non-zero number and any non-zero number to 0.37 But it turns out that we do not need to map any non-zero number to 0: we will use a matrix variable symbol neg, with a validity predicate that expresses that neg interpolates negation as required.

4.2.1 Syntax with arbitrary f and compilation to syntax without

Consider the following scenario:

1. We have some function f : ℚ →ℚ. (For simplicity we assume f is unary, but functions with more arguments can also be accommodated.)

2. We have represented f in our logic with

• a matrix variable symbol f of arity arity(f) ≥ 2, and

• a validity predicate χf, such that f1 represents input values, and f2 represents output values. In symbols, we write:

⊨ς χf=⇒ ∀x ∈1..len(ς(f)). f2(x) = f(f1(x)).

Other rows may be present in f (see for example our implementation of sign in Definition 4.1.7, which requires a third row of data). This is fine and will not affect our reasoning.

3. We have another matrix variable symbol P with arity(P), and suppose P has a validity predicate χP that uses an f-enriched term syntax, which enriches the syntax from Figure 1 such that if t is an f-enriched term then f(t) is an f-enriched term.
There are no other restrictions on χP; it is just some predicate, but in the f-enriched syntax. The denotation of the f-enriched term f(t), is f applied to the denotation of t. That is, we enrich Figure 2 with a clause

⟦f(t)⟧ς(x) = f(⟦t⟧ς(x)). (2)

We want to transform χP into another validity predicate χ′ P such that

• χ′ P means the same thing as χP (in a sense we will make formal in Definition 4.2.3 and Proposition 4.2.4) but

• χ′ P is in the unenriched syntax, and it will replace calls to f with uses of the matrix variable symbol f.

Specifically, in Definition 4.2.3 we will show how to transform

• a matrix variable symbol P with arity arity(P) and validity predicate χP that contains some innermost instance of f(t),38 into

• a matrix variable symbol P′ with arity arity(P′) = arity(P)+1 and a validity predicate χP′ that does not contain this instance of f(t).

Since syntax is finite, we can eliminate all instances of f from our validity predicate by repeating this transformation.

Remark 4.2.2

The transformation outlined in Definition 4.2.3 is straightforward: we replace calls to f with pointers to a matrix that stores a polynomial interpolation with the same values at those calls. A polynomial can approximate a function at any finite number of points, so we know this can work; the rest is just a matter of getting the technicalities right.

Definition 4.2.3 (The transformation).

For clarity, we sugar f1(t) to f.in(t) and f2(t) to f.out(t).

1. Looking at the syntax in Figure 1, we see that the instance of f(t) must occur inside some subpredicate ϕ = (t′ =t′′) where f(t) appears in t′ or t′′. We obtain χP′ from χP by replacing ϕ in χP with

(f.in(P′ n+1(X)) = t) ∧ϕ[f(t)↦ →f.out(P′ n+1(X))],

where ϕ[f(t) ↦→ f.out(P′ n+1(X))] denotes the predicate obtained by replacing any instances of f(t) in ϕ (of which we assumed there is at least one) with f.out(P′ n+1(X)). Using Theorem 2.4.4 we see that χP′ expresses (subject to range checks which we will add below) that the value in P′ n+1(X) points to a column in f that contains (t, f(t)).

2. We repeat the transformation above until there are no mentions of f left. The result is a matrix variable symbol P(n) of arity arity(P(n)) = arity(P) + n (where n is the number of times we applied our transformation), and with validity predicate χP(n).

3. Now we just need to wrap this in range checks to prevent out-of-bounds pointer errors in the extra rows, so we set:

χ′ P = χP(n) ∧(1 ≤P(n) i+1 ≤len(f)) ∧. . . ∧(1 ≤P(n) i+n ≤len(f)).
Proposition 4.2.4

Suppose ς is an interpretation such that ⊨ς χf. Then the following are equivalent:

1. ⊨ς χP in the enriched syntax and denotation described above — in which f(t) is a term if t is a term, and ⟦f(t)⟧ς(x) = f(⟦t⟧ς(x)) as per equation 2.

2. ⊨ς χ′ P in the unenriched semantics.

Proof

The argument is already in Definition 4.2.3: calls to f are replaced by range-checked pointers to columns in f. We have assumed that ⊨ς χf, and we have assumed that this implies that ς(f)2(x) = f(ς(f)1(x)) for every column in ς(f), so that a call to f in the enriched syntax is precisely equivalent to a lookup in ς(f) of a column starting with the denotation of that term.End of proof

Remark 4.2.5

Each step of the transformation in Definition 4.2.3(1) removes one innermost instance of f(t) and increases the arity of the matrix variable symbol by 1 (modulo optimisations, e.g if f(t) appears more than once). So we can say that, roughly speaking,

each function-call to f costs an extra row in the validity matrix.

This is fine because it does not affect the width of the matrices, and so does not increase the degree of the interpolating polynomials.39

Overall, the process described above is not much different from what we do in ordinary mathematics, when we define e.g. Kuratowski pairs as (x, y) = {{x}, {x, y}} and then proceed to use (x, y) directly; or when we define and use functions in any modern programming language and expect that these may be inlined, optimised, or compiled to a lower-level representation. In principle everything will get unwound to some more primitive syntax, so we know we are safe, but the higher-level syntax is more usable.

In a practical implementation of this logic, we might expect to provide functions as primitive, and let the compiler translate them to a lower-level representation as described above.

4.2.2 An application: predicate complementation

We conclude by bringing together what we have learned, to express negation as a macro. In more technical terminology: we will show that our logic is complemented.

Recall from Figures 1 and 2 that our syntax and semantics do not include predicate negation ¬ϕ. This is because we have one ‘true’ truth-value 0, and many ‘false’ truth-values ℚ \ {0}.

However, in the presence of the rest of the logic, the range-check < allows us to implement negation as a macro operation. We saw a strong indication of this in neg and neg from Subsection 4.1.2. This negation acts at the level of terms, but using the ideas in this Subsection we can fold it back into our logic.

Notation 4.2.6 and Theorem 4.2.7 are written in a syntax enriched with neg, as per Subsection 4.2.1:

Notation 4.2.6

Suppose ϕ is a predicate. Then we define ∼ϕ the complement of ϕ by40

∼ϕ as shorthand for neg(reify(ϕ)) = 0.

As described in Proposition 4.2.4, ∼ϕ can be compiled down to an unenriched syntax that assumes a matrix variable symbol neg of arity 3 and a validity predicate χneg as per Definition 4.1.7. This licenses us to work directly with neg-enriched syntax, and we obtain Theorem 4.2.7:

Theorem 4.2.7

Suppose ς is an interpretation and x ∈ℚ and ϕ is a predicate. Then

x ⊨ς ∼ϕ if and only if x ⊭ς ϕ.
Proof

By chasing definitions. The fact that this works is in itself a mathematical result that needs to be checked, so we give full details:

x ⊨ς ∼ϕ ⇐⇒⟦∼ϕ⟧ς(x) = 0 Figure 2⇐⇒⟦neg(reify(ϕ)) = 0⟧ς(x) = 0 Notation 4.2.6⇐⇒(⟦neg(reify(ϕ))⟧ς −0)2(x) = 0 Figure 2⇐⇒⟦neg(reify(ϕ))⟧ς(x) = 0 Fact⇐⇒neg(⟦reify(ϕ)⟧ς(x)) = 0 Equation 2 from Subsection 4.2.1⇐⇒⟦reify(ϕ)⟧ς(x) ≠ 0 Definition 4.1.5⇐⇒⟦ϕ⟧ς(x) ≠ 0 Figure 2⇐⇒x ⊭ς ϕ Figure 2

The use of equation 2 from Subsection 4.2.1 above (i.e. treating neg as a primitive in our syntax) is justified by Proposition 4.2.4.End of proof

Theorems 4.2.7 and 2.4.4 taken together prove that our logic can translate the expressive power of full first-order logic — at least! — into polynomials. Each step towards this is arguably elementary, but the overall result seems surprising and powerful.

4.3 General recursion

We show how to implement a minimisation function, in the sense of general recursive functions [DN24], in our logic.41 The construction below is rather fiddly, but this is worth doing because it demonstrates that our logic is expressive enough to verify general recursion.

We already had a hint of this, because we specified Ackermann’s function in Subsection 3.5 and this is known as a canonical function that is recursive but not primitive recursive. But here, we isolate and implement a minimisation function in and of itself.

Recall the (standard) definition:

Definition 4.3.1

Suppose f : (ℕ≥1 × ℕk) →ℕ.42 Then define the minimisation µ(f) by

µ(f) : ℕk →ℕ µ(f)(x1, . . . , xk) = min{n ∈ℕ≥1 | f(n, x1, . . . , xk) = 0}.

In words: µ(f) maps (x1, . . . , xk) ∈ℕk to the least zero value of λn.f(n, x1, . . . , xk).

If no such zero value exists, so that {n ∈ℕ≥1 | f(n, x1, . . . , xk) = 0} = ∅, then the value of µ(f)(x1, . . . , xk) is not specified.43

Remark 4.3.2

We can think of µ as generalising a while loop: given some parameters (x1, . . . , xk) ∈ ℕk, µ searches n ∈ℕ≥1 and continues while the value of f(n, x1, . . . , xk) ≠ 0. If f(n, x1, . . . , xk) = 0, then µ stops and returns that (first) value of n.

Now we give a slightly lower-level version of Definition 4.3.1. It is still abstract, but it is closer to what we would implement in our logic.

Notation 4.3.3

Suppose U ⊆ℕ≥1 × ℕ and b ∈ℕ. Then define

Ub = {a ∈ℕ≥1 | (a, b) ∈U}.

If Ub is an initial segment of ℕ≥1 for every b ∈ℕ, then call U initial in its first component.44

Recall that sign is defined in Definition 4.1.5, and note that if we restrict sign to ℕ then it maps to {0, 1}.

Definition 4.3.4

Assume we are given the following data:

1. A function f : (ℕ≥1 × ℕ) →ℕ (i.e. for simplicity we have set k = 1 in Definition 4.3.1).

2. A U ⊆ℕ≥1 × ℕ that is initial in its first component (Notation 4.3.3).

We specify a pair of functions

minf,U, accf,U : U →ℕ

(minf,U is short for ‘minimal point’ and accf,U is short for ‘accumulator’) as follows:

1 ≤minf,U(a, b) a≠1 =⇒minf,U(a, b) = minf,U(a−1, b) f(minf,U(a, b), b) ≤f(a, b) a=1 =⇒accf,U(a, b) = sign(f(a, b) −f(minf,U(a, b), b)) a≠1 =⇒accf,U(a, b) = accf,U(a−1, b) ∗sign(f(a, b)−f(minf,U(a, b), b)) minf,U(a, b)≠1 =⇒accf,U(minf,U(a, b)−1, b) = 1

We make sense of Definition 4.3.4 using a lemma:

Lemma 4.3.5

Continuing the notation of Definition 4.3.4, we have the following properties, for each b ∈ℕ:

1. λa∈Ub.minf,U(a, b) is a constant function into ℕ≥1. Write µf,U(b) ∈ℕ≥1 for its unique value.

2. f(µf,U(b), b) ≤f(a, b) for every a ∈Ub. Thus, f(µf,U(b), b) is a lower bound for {f(a, b) | a ∈Ub}.

3. Furthermore, since f(µf,U(b), b) = f(µf,U(b), b), also f(µf,U(b)) is a greatest lower bound for this set. Thus,

µf,U(b) ∈ℕ≥1 is the index of a minimal value of λa∈Ub.f(n, b).

4. accf,U(a, b) = ∏i∈1..a sign(f(a, b) −µf,U(b)). We observe by arithmetic that this is equal to 1 or 0, and accf,U(a, b) is equal to 0 precisely when f(i, b) = f(µf,U(b), b) for some i ∈ 1..a.

5. If µf,U(b) > 1 then accf,U(µf,U(b) − 1, b) = 1, which means that µf,U(b) ⪇f(a, b) for every 1 ≤a < µf,U(b). Thus,

µf,U(b) is also least such that λa∈Ub.f(a, b) attains its minimal value.

muf,1(X) sugars to ptr.min(X) muf,2(X) sugars to ptr.f(X)f1(ptr.f(X)) sugars to a(X) f2(ptr.f(X)) sugars to b(X) f3(ptr.f(X)) sugars to f.ab(X)muf,3(X) sugars to acc(X) muf,4(X) sugars to ptr.prev(X) Write t ≠ t′ as shorthand for sign(t −t′)2 = 1. Write t ≤t′ as shorthand for sign(t −t′ + 1) = 1. χµf = 1 ≤ptr.min ≤len(mu) ∧1 ≤ptr.prev ≤len(mu) ∧1 ≤ptr.f ≤len(f)∧ ∀muX.((a(X) = 1 ∨ptr.min(ptr.prev(X)) = ptr.min(X)) ∧ (f.ab(ptr.min(X)) ≤f.ab(X)) ∧ (a(X) = 1 ∧acc(X) = sign(f.ab(X) −f.ab(ptr.min(X))))∨(a(X) ≠ 1 ∧acc(X) = sign(f.ab(X) − f.ab(ptr.min(X))) ∗acc(ptr.prev(X))) ∧(a(ptr.min(X)) = 1 ∨acc(ptr.prev(X)) = 1) ∧ (a(X) = 1 ∨a(ptr.prev(X)) = a(X) −1) ∧ (a(X) = 1 ∨b(ptr.prev(X)) = b(X)))
Figure 9: Expressing a minimisation operator µ (Definition 4.3.6)
Proof

Direct from the construction, as described in the statement of this Lemma.End of proof

We can now implement minimisation in our logic, just by translating Definition 4.3.4 into it:

Definition 4.3.6

Suppose we are given a matrix variable symbol f whose first three rows f1, f2, and f3 are intended to represent the two input values a and b and one output value f(a, b) of a binary function f : (ℕ≥1 × ℕ) →ℕ.

Assume a matrix variable symbol muf with arity arity(mu) = 4. In Figure 9, we define syntactic sugar and use it to express a validity predicate χµf, based on Definition 4.3.4.

Remark 4.3.7

Note that in the predicate χµf in Figure 9, we use the function sign from Definition 4.1.5 directly in terms. Its implementation in matrix semantics is in Definition 4.1.7.

We can do this because as per Subsection 4.2, the function call can be compiled down to the purely polynomial term language. This is not a problem and our presentation in Figure 9 is more readable as a result.

A simple and natural bit of terminology will be useful in a moment:

Definition 4.3.8

Suppose that:

1. f : (ℕ≥1 × ℕ) →ℕ.

2. f with arity arity(f) ≥ 3 is a matrix variable symbol.

3. ς is an interpretation.

Then say that ς interprets f when

ς(f)3(x) = f(ς(f)1(x), ς(f)2(x))

for every x ∈ 1..len(ς(f)).

Proposition 4.3.9

Suppose f : (ℕ≥1 × ℕ) →ℕ, and f with arity arity(f) ≥ 3 is a matrix variable symbol, and suppose ς is an interpretation that interprets f (Definition 4.3.8). Then

• if ⊨ς χµf (Figure 9),

• then ⟦ptr.min(X)⟧ς(x) = µf,U(⟦b(X)⟧ς(x)),

where we define U ⊆ℕ≥1 × ℕ by

U ={⟦a(X)⟧ς(x), ⟦b(X)⟧ς(x) | x ∈1..len(ς(mu))}

(this is just a fancy way of setting U to be the set of (a, b) pairs over which ς(mu) minimises).

Proof

We examine Figure 9 and see through careful inspection that it translates Definition 4.3.4 into our logic: ς(muf)1 corresponds to minf,U and ς(muf)2 corresponds to accf,U.End of proof

Remark 4.3.10

Proposition 4.3.9 does not describe the full minimisation outlined in Definition 4.3.1, but this is only because minimisation implicitly contains an unbounded search, whereas an interpretation ς delivers finite matrices.

This is reasonable, because it is the prover’s job to run a program and — after a finite time — it must stop and present the ς it has generated. If the prover does not terminate then no ς is generated and there is nothing for the verifier to do. So in our context, minimisation means finding minimal values within a given run.

Thus Proposition 4.3.9 does the reasonable thing, which is to tell us that if we are given some b ∈ℕ and a ∈ℕ≥1 and a ς that satisfies the validation predicates and for which ς(mu) contains a column which references f(a, b) — if all the above holds, then ς(mu) correctly identifies the first index i ∈ 1..a to yield the lowest value of f(i, b).

4.4 Logic gates

We conclude with a small detour: how to encode a circuit of logic gates in our framework.

In one sense, considering logic gates is a waste: we already have predicates and terms, which are higher-level and (as we have seen) compile to polynomials. Yet it is still an interesting exercise to spell out how this might be done.

We will only implement a nand gate; this is known to be a universal logic gate from which all others may be derived (see [Kup24] for a clear presentation), and it will also be completely clear from the example of nand below how other logic gates could be directly implemented.

Recall from Remark 2.3.5(1) that we model 0 as ‘true’ and 1 as ‘false’, so the bits are flipped. nand should return 1 (false) if both of its inputs are 0 (true), and 0 (true) otherwise.

Definition 4.4.1

It is straightforward to encode NAND as a simple polynomial:

nand(a, b) = (1 −a) ∗(1 −b).

Now we want to connect our individual logic gates into circuits.

We could try to nest our gates as functions, but we see from Remark 3.2.12(4) that this would result in polynomials of high degree; a more efficient method is available.

Definition 4.4.2

Assume a matrix variable symbol nand with arity arity(nand) = 5. In Figure 10, we define syntactic sugar and use it to express a validity predicate χnand, based on Definition 4.4.1.

nand1(X) sugars to nand.in1(X) nand2(X) sugars to nand.in2(X)nand3(X) sugars to nand.out(X) nand4(X) sugars to in1.ptr(X) nand5(X) sugars to in2.ptr(X) χnand = 0 ≤in1.ptr ≤len(nand) ∧0 ≤in2.ptr ≤len(nand) ∧ ∀nandX.((nand.out(X) = (1 −nand.in1(X)) ∗(1 −nand.in2(X))) ∧ (in1.ptr(X) = 0 ∨nand.out(in1.ptr(X)) = nand.in1(X)) ∧ (in2.ptr(X) = 0 ∨nand.out(in2.ptr(X)) = nand.in2(X)) ∧ (nand.in1(X) = 0 ∨nand.in1(X) = 1) ∧ (nand.in2(X) = 0 ∨nand.in2(X) = 1))
Figure 10: Expressing a circuit of NAND gates (Definition 4.4.2)
Remark 4.4.3

We read through this carefully. Suppose we are given an interpretation ς and consider column number x in ς(nand), which is a 5-tuple of elements (a, b, r, p1, p2) ∈ℤ5:

1. a represents the first argument to the NAND gate. This must be equal to either 0 or 1.45

2. b represents the second argument to the NAND gate.

3. r represents the result. Note that χnand insists that r = nand(a, b).

4. p1 represents either a null pointer 0, or it is a pointer to the output of some other gate. Note that χnand insists that the value of that output is equal to a; thus we ‘wire’ the output to the first input of this gate.

5. Similarly for p2.

Visibly this implements a circuit of NAND gates, where input wires are ones such that p1 (or p2) is zero, and output wires are outputs that are not pointed to.46 A more explicit encoding would also be possible, but this will do.

Remark 4.4.4

1. Circuits with multiple types of gate (AND, OR, NOT) could be encoded, either as distinct matrix variable symbols with their own validity predicates, or by generalising Figure 10 directly with an additional row of data to describe what type of gate is stored.

2. The degree of the polynomial ⟦χnand⟧ς scales as O(n2), where n is len(ς(nand)). Our framework is not optimised for the special case of representing a circuit of simple logic gates, but if we specialise anyway then this does not obviously incur any serious overhead.

5 Efficiency: succinctness and built-in functions

5.1 Schwartz-Zippel

We give the reader a flavour of how the polynomial semantics can be applied.

Recall the arithmetisation of valid SK-combinator reduction χevl from Subsection 3.9, and for simplicity write it in the form ∀evlX.ϕ for suitable ϕ. Suppose a prover wants to convince a verifier that ⊨ς ∀evlX.ϕ, where the first column in ς(evl) encodes some evaluation of a large and complicated SK-combinator term. For brevity write n = len(ς(evl)). The verifier could check that ⟦ϕ[X:=i]⟧ς = 0 for every i ∈ 1..n, but that could be quite slow if n is large. Instead, the prover can compute a factorisation ⟦ϕ⟧ς = h ∗ zeroesn, where

zeroesn =∏i∈1..n(X−i) ∈ℚ[X], (3)

and h ∈ℚ[X] is the result of a long division ⟦ϕ⟧ς/zeroesn, which has zero remainder because we assumed that ⟦ϕ⟧ς has roots at 1..n.

By the Schwartz-Zippel lemma, polynomial equality and evaluation at a random point are equivalent, to a high degree of probability (see [Tha22, Lemma 3.3, Subsection 3.4] or [Lip09]):47

Lemma 5.1.1 (Schwartz-Zippel).

Suppose P ∈𝔽[X] is a nonzero polynomial of degree d, over a field 𝔽, where 𝔽 is much larger than d. (𝔽 could be a finite field, but it could also be ℚ.)

Suppose S ⊆fin 𝔽 is a finite subset of 𝔽 and write #S for the cardinality of (number of elements in) S. Then:

1. For a randomly chosen x ∈S, the probability of P(x) being zero is at most d/#S. Thus as #S becomes very large relative to d, P(x) ≠ 0 with a very high probability.48

2. As a corollary, if P, Q ∈𝔽[X] then with a high degree of probability for large S the following are equivalent:

• P = Q (P and Q are identical polynomials).

• P(x) = Q(x) at a randomly-chosen x ∈S (P and Q evaluate to the same value at a random point).

Proof

P has at most d roots. If #S/d is large, x is probably not one of them. The corollary follows taking P −Q.End of proof

Lemma 5.1.2

1. If ⟦ϕ⟧ς(q) = h(q) ∗ zeroesn(q) for a random q ∈ℚ then ⟦ϕ⟧ς = h∗ zeroesn to a high degree of probability.

2. As a corollary, to check ⊨ς ∀evlX.ϕ it suffices to pick a random q ∈ℚ and check the equality above, for n = len(evl).

Proof

We just apply Lemma 5.1.1 to ⟦ϕ⟧ς and hC,ϕ ∗zeroeslen(ς(C)) in ℚ[X]. The corollary follows by the discussion above.End of proof

Remark 5.1.3

The proof-scheme above is representative of a style of cryptographic proof, in the sense that many cryptographic proof-schemes work by the verifier sampling polynomials at randomly-chosen points.

Note that on its own, this scheme is too simplistic to be practical. A nice elementary exposition of how to build from Schwartz-Zippel to something more practical is online [AT20]. Here, we will put things in context:

1. The scheme above is not succinct: the prover has to communicate all of ς(evl) to the verifier. If this is large (e.g. gigabytes or terabytes) then that puts strain on the communication channel and on the verifier’s memory. A succinct proof-scheme can attain near certainty about validity, without being bottlenecked by the network or the verifier’s power.

2. The scheme above is not zero-knowledge. The prover reveals ς(evl) to the verifier; it might want to keep it secret. A zero knowledge proof-scheme can attain near certainty without revealing the witnessing data in ς to the verifier.

3. The computations above use the field of rationals ℚ, so there is no bound on the possible magnitude of the individual numbers involved. Practical proof-schemes usually use a finite field 𝔽.

4. The range-check primitive t < C is neither succinct nor zero-knowledge, at least if the prover just sends ς(C) to the verifier to check the range. Range-check schemes are well-studied, and are a special case of succinct (and zero knowledge) set membership schemes. This is a field of research in is own right ([BCF+23] contains a recent survey).

It remains to refine the FOL semantics to generate polynomials of a suitable form for efficiently interfacing with cryptographic methods, and / or create a suitable cryptographic scheme of our own; see the discussion of future work in Remark 6.1.1. It would also be helpful to educate the wider (non-logic) community on techniques from logic and computation, such as induction, derivation-trees, the distinction between syntax and semantics, the concept of computation existing independently of a virtual machine, and logical specification of correctness properties as a separate thing from execution of the code itself.49

5.2 Built-in functions

Having touched on notions of efficiency in the previous Subsection, we now make a few observations about making things run quickly on native silicon (i.e. directly on the underlying processor hardware). In this case, we may prefer to check some validity properties directly:

1. We gave a polynomial circuit to check that a matrix expresses bitwise expansion of 64-bit unsigned integers in Subsection 3.6. But bitwise operations may be rapid on underlying hardware — not least because this is how numbers are represented anyway. In practice, rather than check a validity predicate, a verifier might recognise that this is a bitwise expansion operation and prefer to just traverse the matrix and check its correctness directly. In a monolithic system, where everything has to run in an abstract machine built in arithmetic circuits, this might be a bit problematic because it would involve stepping outside the abstraction provided. The system we describe in this paper is quite modular, so this may be less of a problem.

2. The range check primitive < in Figure 1 can be checked rapidly in silicon.
If we are just using < to range check that pointers are in bound for the matrices they point to, then information leakage would be minimal: all a validator would have is a set of pointers, but without knowing how the prover has laid out its data in its matrices, this does not impart much useful information. For extra security, the numbers could always be obfuscated. Concretely, we would do this by providing pos from Definition 4.1.2 as a built-in matrix variable symbol of infinite length — calls to the validity check of pos would just get passed

directly to the underlying silicon. As per Remark 4.1.10, just providing this would provide all the power of <.

So we see that if we just care about speed, then efficient checking in silicon for a small set of special built-in validity predicates, like range checks and bitwise operations, should be fine. If we want a full zero-knowledge treatment, such that the verifier never learns the precise witnesses used, this would not be possible.

But even here, we might (depending on circumstances) be happy to accept a small amount of information leakage, if this buys us enough efficiency. In particular, range checks for pointers could be done outside of a zero knowledge wrapper and information leakage may be acceptable, if all the verifier has is a bunch of pointers but no information about what they point to or how they connect. This seems plausible, but working through how to do it in practice is future work.

6 Conclusions and further work

6.1 Future work and other observations

Remark 6.1.1

There are plenty of directions to go from here. For example:

1. Implementation. We have set up a shallow translation from logic to polynomials, and from logical judgements to polynomial equality judgements. An obvious next step is to engineer a practical cryptographic proving system based on these ideas.
This is current work and we will do no more here than sketch one high-level design choice: which polynomial ring to map to.
In this paper we use rational polynomials ℚ[X], but cryptographic methods often (though not universally) use polynomials over finite fields; e.g. 𝔽[X] where 𝔽 is a finite field. If we switch to polynomials over a finite field then the character of the semantics changes in several ways. Most immediately, the mapping ⟦ϕ ∧ϕ′⟧ = ⟦ϕ⟧ + ⟦ϕ′⟧ is compromised, because in a finite field the sum of two nonzero numbers is not necessarily nonzero. Various possibilities exist to overcome this, including: we set ⟦ϕ ∧ϕ′⟧ = gcd(⟦ϕ⟧, ⟦ϕ′⟧) (greatest common divisor); or we set ⟦ϕ ∧ϕ′⟧ = Z ∗ ⟦ϕ⟧ + Z′ ∗ ⟦ϕ′⟧ where Z and Z′ are indeterminates (variable symbols, similar to the X in Definition 2.2.3) representing randomly-chosen numbers. However, it may also be that rational polynomials are practical as is. Very recent work (announced after this material was drafted) argues for cryptographic proof-schemes over rational polynomials and proposes a system that can work with them directly [GWHD25]. The pace of change in this field is rapid; perhaps cryptography is growing towards this material as quickly as this material is growing towards cryptography.

2. HOL and other more expressive logics. We have considered a first-order logic in this paper. What about other logics; for example a higher-order logic? We see no barrier to this. Indeed in a certain sense we have already taken the key step towards this when we considered arbitrary functions in Subsection 4.2. As we note in Remark 4.2.1, the model-theoretic power of the logic — HOL vs FOL, for example — is not so important here, because we are only interested in behaviour at finitely many points so we can interpolate it with a polynomial. We consider FOL in this paper because it is a simple system and so useful for proof-of-logical-concept, but the techniques should generalise. For a precise and technical expression of a related point, see Remark 6.1.2, which notes that the logic in this paper is FOL, but it is not just FOL.

3. Polynomial-inspired logical systems. In the discussion up to now, we have considered a preexisting logic (FOL) and given it a polynomial semantics. But the ideas could flow in the other direction as well, from semantics to logic, and we can ask: what logics does the polynomial semantics suggest? For a start, we can consider constructs inspired by polynomial division. Define P \ Q to be P with any roots it shares with Q divided out. This would model non-implication ϕ ⇏ ψ

(which can also be written as ϕ ∧¬ψ). See also next point.

4. Resource-sensitive logics. Following the previous point, a polynomial can be viewed as a multisets of roots. Thus it is natural to finesse our logic to make it resource-sensitive, in the sense of linear logic or logics with subexponentials. The validity judgement of our logic is clean and simple

x ⊨ς ϕ ⇐⇒⟦ϕ⟧ς(x) = 0,

as per Figure 2. It just says that x is a root of ⟦ϕ⟧ς. But polynomials, being multisets of roots, suggest other validity judgements. For example, it is natural to consider

⊨ς (Φ ⊢ψ) ⇐⇒(∑ϕ∈Φ⟦ϕ⟧ς) | ⟦ψ⟧ς

corresponding to an assertion that Φ implies ψ.50 This notion of validity has some element of resource-sensitivity, because divisibility includes root multiplicity.51 The design space of logics here seems interesting and merits investigation.

5. Multivariate polynomials. Our polynomials are univariate, and correspondingly our first-order logic has just one variable symbol X (and arbitrarily many matrix variable symbols). It would be natural to generalise to the multivariate case — thus permitting X, but also X′ and Y , and so on, in Figure 1. This would naturally give a translation to multivariate first-order logic, just by setting ⟦X′⟧ = X′ for each variable symbols in Figure 2. Nothing in the maths in Figure 2 would be affected.
This might be convenient and useful for applying multivariate arithmetisation techniques, but we do not think it would increase expressivity. It seems likely that we could emulate the multivariate case using Skolem functions (see next point) and (functions representing) ϵ-terms [AZ20]. Looking into this generalisation is future work.

6. Skolem functions. We include an existential quantifier ∃ in our syntax and semantics, but in practice a more efficient technique might be to use Skolem functions [AZ20]. A Skolem function is just a way to replace an existential quantifier with a function symbol; e.g. ∀x.∃y.x = y becomes ∃f.∀x.x = f(x). The f can then be compiled down to a matrix variable symbol in our base syntax, using the techniques in Subsection 4.2. Thus mathematically, one way to view our matrix variable symbols is as Skolem symbols.

7. Tree-structured data. Tree-structured data is used pervasively in declarative programming. In light of this paper, it would be interesting to give labelled trees additive and multiplicative structure sufficient to do polynomial arithmetic directly over trees (something along these lines has been done [Tar16]) so that, instead of working as we do in this paper with a ring of polynomials over rationals (ℚ[X]), we could work with a ring of polynomials over trees: Tree[X]. Integers can already emulate trees via a Gödel encoding, but if we had polynomials with coefficients that already are trees, then we might be able to avoid some encoding and decoding. This is speculative but it is an interesting motivation for future work.

Remark 6.1.2

How powerful is our logic, really? In fact, extremely powerful!

The syntax in Figure 1 has a term-former reify that maps predicates back down to terms. This reflects the fact that in our semantics, terms map to polynomials, and so do predicates (predicates map to non-negative polynomials, but a non-negative polynomial is still just a polynomial).

This is unusual and it makes the logic impredicative. We have called our logic ‘first-order logic’ — and this was not untrue since it comes with a specific intended model in which the variable X ranges over numbers. But what that left unsaid at the start, for simplicity, was that our logic also has an in-built mapping between predicates and terms; with reify going from predicates to terms, and t = 0 going from terms to predicates (cf. Remark 2.4.6).52

So this is FOL, but not just FOL, and the full expressivity of the syntax in Figure 1, with its intended semantics in Figure 2 is a topic for future research.

6.2 More on efficiency

We discussed efficiency and succinctness in Remarks 3.2.12 and 3.4.6(2). We make a few more general observations, based on the following question:

How big do our polynomials get?

Remark 6.2.1

1. When we succinctly check a polynomial equality

⟦ϕ⟧ς(q) = hC,ϕ(q) ∗zeroeslen(ς(C))(q),

(zeroes is defined in equation (3) in Subsection 5.1) lower-degree polynomials are better because a) they are easier to evaluate and b) they have fewer roots (so that a succinct check is less likely to give a false positive). So we can ask what contributes to the degree of the polynomial that is ⟦ϕ⟧ς. We discussed this in the context of a simple but paradigmatic example in Remark 3.2.12. One important point is that ∧ maps to addition, which does not increase degree — we can say: conjunction is free. Thus, succinctly checking a conjunction of validity predicates is no more expensive than checking the most expensive (= highest degree) clause. Thus, a program consisting of a large number of matrix variable symbols with relatively simple, low-degree validity predicates, is better than a program with a smaller number of matrix variable symbols with more complex validity predicates. This fits in nicely with a modular programming philosophy, where we try to factor our system into a many relatively simple parts. The reader will know that factoring a system into smaller pieces, where possible, is generally accepted as good practice anyway — but here it has concrete mathematical implications: we get lower degree polynomials.

2. Having matrices with lots of rows is cheap, because rows do not directly increase the degree of polynomials. Long interpolation vectors cost, because (as we noted in Definition 2.1.4(2) and Remark 3.2.12(5)) a vector of length n requires in general a degree n−1 interpolating polynomial. So we want to design our validation predicates to create tall but narrow matrices.

3. So our question becomes:

What leads to wide matrices?

Broadly speaking, this is bounded by how many distinct function calls are made overall (‘distinct’, because the system is naturally memoised; see Remark 3.4.6(2)). Counting such calls is a familiar task; for example, exponentiation ab can be computed in O(ln(b)) distinct calls (as discussed in Remark 3.2.14). So after all this discussion, our conclusion is fairly straightforward:

(a) computation and control flow are free, and

(b) the cost of verification scales with the size of the longest deduplicated derivation chain.

Broadly speaking, this corresponds to the inherent complexity of proving something, so we can say that our translation is efficient in the sense that it converts a logical problem into an arithmetic one of roughly equal (and thus not much larger) complexity.

6.3 Other comments

Remark 6.3.1 (Logic programming).

Logic programming can be understood as the engineering of predicates and derivation rules to make the search for derivation-trees computationally efficient (an old but to-the-point research survey is in [MNPS91]).

Our examples in Section 3 show how we can encode computation as derivation-trees, as is standard in mathematically structured programming. A so-called validity predicate χC expresses when a matrix ς(C) expresses a valid derivation-tree, and thus a valid computation. The reader can think of ς(C) as being a kind of ‘generalised computation trace’ (but remember this is very general, and in particular derivation trees need not be linear).

Given that this paper uses derivation-trees, and so does logic programming, is there a connection? Yes, and no.

For us in this paper, finding a valid derivation-tree / providing a suitable ς, is for the prover. Many methods for generating derivation-trees exist — including logic-programming systems, but also rewrite systems, or just by some suitable evaluation strategy. What is true is that logic programming is one way to efficiently construct derivation-trees, and our semantics consumes them, so there is a natural match here.

Remark 6.3.2 (Why matrices?).

Why do we need matrices variable symbols in Figure 2? Why not just encode all our information into natural numbers, as we do e.g. when we use a Cantor pairing function to Gödel encode combinator terms in Definition 3.9.4? Why not just do this or something like it throughout?

We could try, but a key issue is our use of pointers. The reader can see in the examples in Section 3 how we use entries in our matrices to point to columns in matrices (we make an effort to really spell this out in Examples 3.2.8 and 3.2.9). If we Gödel encode all structure in natural numbers, then this would be harder to do because we would have to unpack those pointers from the encoding before using them. This is not necessarily impossible, but it would add layers of complexity which for now we prefer to do without.

To put this another way: we use derivation-trees a lot in our semantics, and trees are graphs, and graphs are labelled nodes with edges. There is a natural structural map from here to matrices, and thence to interpolating polynomials and succinct proofs in the cryptographic sense. Other design decisions may be possible, but this paper follows a(n in retrospect) natural structural path through the mathematics.

Remark 6.3.3 (FOL truth vs. FOL derivability).

This paper maps FOL judgements directly to polynomial equalities (Figure 2), such that valid (true) judgements map to valid (true) equalities.

Another approach to encoding FOL is to map its syntax and derivation-trees to polynomials with a circuit that identifies the (encodings of) well-formed derivation trees. That is also a good approach, but it encodes derivability, not validity.

To see how these differ, consider the FOL predicate 0 = 0. This is valid, since 0 is equal to 0; and it is derivable by the equality right-derivation rule. As per Figure 2 ⟦0 = 0⟧ς = 0, which represents ‘true’. Thus, ⟦0 = 0⟧ς is true because it literally is true; indeed no reasoning or circuitry is required in this case; it is just a fact! An arithmetisation of FOL that uses derivability would encode a (simple) derivation tree like this

(=R)⊢0 = 0

along with a circuit expressing that this is well-formed.53 It makes sense, but it is a different approach.

It is the difference between asserting ‘∀x.∃y.x = y is true in some finite model’ and ‘I have a valid derivation-tree of ∀x.∃y.x = y’. The former is a (true) assertion about concrete behaviour in finite models (finite, because ς is unbounded, but finite), whereas the latter is an assertion about derivability.

For computation, finite models are what matters most, so our design choice is natural. We labour this point because derivation-trees still feature in this paper but they arise in the spirit of being generalised computation traces; the embedding of the FOL logic remains semantic and direct as discussed above. An ‘infinite models’ version of the ideas in this paper, possibly working through explicit consideration of FOL derivation-trees, is possible future work.

Remark 6.3.4 (Rapid coprocessors).

We could use the ideas in this paper for fast and efficient prototyping of a correct-by-construction coprocessor for an existing system: to create some function, specified and arithmetised using the techniques in this paper, for the specific purpose of being called from some other zero-knowledge abstract machine.

We have seen how the compositional nature of our semantics lends itself — by design — to specifying functional programs, which require no external state and which are correct by construction.54 Functional components are modular and compositional, and therefore portable and well-suited to being plugged together.

This compositionality could be useful and may mean that the barrier to extracting practical value from these ideas may be relatively low.

Furthermore, pure speed is not the only metric of success: shorter development time, greater modularity, readability, maintainability, portability, and amenability to formal verification of correctness, are also valid criteria, amongst others. High-level specifications tend to perform well by these metrics, so a compositional shallow translation directly to polynomials is interesting.

6.4 Final remarks

The fundamental substrate of cryptography is polynomials, whereas the fundamental substrate of logic and computation is formal logic and Boolean semantics. First-order logic is a simple but powerful logic and in this paper we have given it a polynomial-based notion of validity.

Specifically, we map predicates to polynomials, and FOL validity judgements to polynomial equalities. At a high level, the mapping is simple:

1. Truth maps to zero, and falsity maps to one.

2. ∧ and ∀ map to +, and ∨ and ∃ map to ∗ (see Figure 2 and the discussion in Remark 3.2.12).

Then simple facts of arithmetic — notably that a sum of two nonnegative numbers is zero if and only if both numbers are zero (Lemma 2.4.2) — give us a soundness and completeness result (Theorem 2.4.4).

It is perhaps surprising that from this elementary beginning, we manage to pull out so much logical and computational content.

Using matrix variable symbols and some simple logic, we specify a library of exemplar functions (Sections 3 and 4), including the Turing-complete SK-combinator system.

In the judgement ⊨ς ϕ for ϕ a closed predicate in Definition 2.3.2(4):

• The predicate ϕ corresponds to what cryptographers would call the instance. This is publicly known data that determines the problem to be solved.

• The interpretation ς of the matrix variable symbols (ς maps them to matrices, and thus to polynomials via interpolation) corresponds to what cryptographers would call a witness. This information is known to the prover but not necessarily to anyone else.

The point of cryptographically verified computation is to devise ways for the prover, given a ϕ, to efficiently (the technical term is succinctly) and perhaps confidentially (in zero knowledge) prove knowledge of a witness ς that makes ϕ valid.

Note that the interpretation ς may have arbitrary size; the size of the interpretation ς and the size of the validity predicate ϕ are orthogonal parameters. Even a simple and compact validity predicate (like the one in Figure 8) can express the correctness of an arbitrarily complex computation trace as encoded in ς.55 Furthermore, computations correspond to derivations (in the style of mathematically structured programming), which are trees: they are not restricted to being a linear trace. Finally, we note that the range check primitive acts in the context of our logic as a truth modality (see Remark 4.1.11) and using this we can encode even more interesting structure (see Section 4).

Our mapping of logical assertions to polynomial equalities (Definition 2.3.2(3)) is clean, compositional, and modular, and overheads seem to be pleasingly low. We get a nice mapping from derivation-trees to matrices, and modularity in the specification corresponds to relatively lower degree polynomials. Practical application is plausible both in and of itself, and as a coprocessor for other systems.

Because this system is based on logic, implementations are likely to be amenable to powerful techniques from computer science, including algebraic and logic-based optimisation techniques, formal verification, correctness-by-construction, and type systems. Although not everything in this paper is elementary, it is noteworthy that the complexities that arise come from the applications, and not from the translation of the logic, which is simple and direct. In other words: our logic and its polynomial translation do not seem to make a thing any harder than it inherently already is. For instance: a ∧ turns into a + and a ∨ turns into ∗, thus one connective = one arithmetic operation. It is hard to imagine a more transparent translation!

Finally, logics other than first-order logic exist, so implicit in the act of mapping of this logic to polynomials is that we might do the same for others — and conversely, there is a possibility for logicians to create interesting new logics inspired by polynomial semantics like the one we present here.

This paper spans two fields with long mathematical traditions: cryptography and formal logic. Cryptography has historically been about encryption — but thanks to the rise of distributed systems, cloud computing, and blockchains, the focus of interest in the field has come nearer to what logicians and programmers do. Thus cryptography is increasingly interested in, and also interesting to, the theory of logic and computation. I hope this paper can promote further collaboration and transfer of ideas between these fields.

References

[ABG+23]Nada Amin, John Burnham, François Garillot, Rosario Gennaro, Chhi’mèd Künzang, Daniel Rogozin, and Cameron Wong. LURK: Lambda, the ultimate recursive knowledge. Cryptology ePrint Archive, Paper 2023/369, 2023. URL: https://eprint.iacr.org/2023/369, doi:10.1145/3607839.

[AT20]Ittai Abraham and Alin Tomescu. A simple and succinct zero knowledge proof. Tutorial blog post at https://decentralizedthoughts.github.io/2020-12-08-a-simple-and-succinct-zero-knowledge-proof/ (permalink), December 2020.

[AZ20]Jeremy Avigad and Richard Zach. The Epsilon Calculus. In Edward N. Zalta, editor, The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University, Fall 2020 edition, 2020.

[Bar84]Henk P. Barendregt. The Lambda Calculus: its Syntax and Semantics (revised ed.), volume 103 of Studies in Logic and the Foundations of Mathematics. North-Holland, 1984. URL: http://www.andrew.cmu.edu/user/cebrown/notes/barendregt.html.

[BCF+23]Daniel Benarroch, Matteo Campanelli, Dario Fiore, Kobi Gurkan, and Dimitris Kolonelos. Zero-knowledge proofs for set membership: efficient, succinct, modular. Designs, Codes and Cryptography, 91(11):3457–3525, Nov 2023. doi:10.1007/s10623-023-01245-1.

[Bim20]Katalin Bimbó. Combinatory Logic. In Edward N. Zalta, editor, The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University, Winter 2020 edition, 2020.

[Cap20]Manuel Capel. The fastest way to compute the Fibonacci sequence. Blog post at https://mancap314.github.io/fastest-fibonacci.html (permalink), August 2020.

[Cha25]Jeffrey R. Chasnov. Numerical methods. Hong Kong University of Science and Technology, 9 2025. Course notes available online at https://batch.libretexts.org/print/Letter/Finished/math-96025/Full.pdf.

[Das18]Ali Dasdan. Twelve simple algorithms to compute Fibonacci numbers, 2018. Available at https://arxiv.org/abs/1803.07199. arXiv:1803.07199.

[DFGK14]George Danezis, Cédric Fournet, Jens Groth, and Markulf Kohlweiss. Square span programs with applications to succinct NIZK arguments. In Palash Sarkar and Tetsu Iwata, editors, Advances in Cryptology – ASIACRYPT 2014, pages 532–550, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg.

[DMaN24]Atze Dijkstra, José Pedro Magalhães, and Pierre Néron. Functional programming in financial markets (experience report). In Proceedings of the International Conference on Functional Programming 2024 (ICFP 2024), volume 8, pages 234 – 248, New York, NY, USA, August 2024. Association for Computing Machinery. Article number 244, available at https://doi.org/10.1145/3674633. doi:10.1145/3674633.

[DN24]Walter Dean and Alberto Naibo. Recursive Functions. In Edward N. Zalta and Uri Nodelman, editors, The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University, Summer 2024 edition, 2024. https://plato.stanford.edu/entries/recursive-functions/ (permalink).

[GWHD25] Albert Garreta, Hendrik Waldner, Katerina Hristova, and Luca Dall’Ava. Zinc: Succinct arguments with small arithmetization overheads from IOPs of proximity to the integers. Cryptology ePrint Archive, Paper 2025/316, 2025. Available at https://eprint.iacr.org/2025/316.

[Kle43]Stephen C. Kleene. Recursive predicates and quantifiers. Transactions of the American Mathematical Society, 53:41–73, 1943. Available online at https://www.ams.org/journals/tran/1943-053-01/S0002-9947-1943-0007371-8/S0002-9947-1943-0007371-8.pdf (permalink).

[Kup24]Tony R. Kuphaldt. Gate universality. In Lessons in Electric Circuits. All about circuits, Accessed 2024. Free online textbook, available at https://www.allaboutcircuits.com/textbook/digital/chpt-3/gate-universality/ (permalink).

[KvOvR93] Jan-Willem Klop, Vincent van Oostrom, and Femke van Raamsdonk. Combinatory reduction systems, introduction and survey. Theoretical Computer Science, 121:279– 308, 1993.

[Lam24]LambdaClass blog. Our highly subjective view on the history of zero-knowledge proofs. https://blog.lambdaclass.com/our-highly-subjective-view-on-the-history-of-zero-knowledge-proofs/ (permalink, February 2024. Accessed: 2025 08 16.

[LCL+24]Xi Lin, Heyang Cao, Feng-Hao Liu, Zhedong Wang, and Mingsheng Wang. Shorter ZK-SNARKs from square span programs over ideal lattices. Cybersecurity, 7(1):33, Mar 2024. doi:10.1186/s42400-024-00215-x.

[Lip09]Richard Lipton. The curious history of the Schwartz-Zippel lemma. Online blog post available at https://rjlipton.com/2009/11/30/the-curious-history-of-the-schwartz-zippel-lemma/ (permalink), November 2009.

[MNPS91]Dale Miller, Gopalan Nadathur, Frank Pfenning, and Andre Scedrov. Uniform proofs as a foundation for logic programming. Annals of Pure and Applied Logic, 51(1):125– 157, 1991. Available at https://doi.org/10.1016/0168-0072(91)90068-W. doi:10.1016/0168-0072(91)90068-W.

[Nat16]Melvyn B. Nathanson. Cantor Polynomials and the Fueter-Pólya Theorem. The American Mathematical Monthly, 123(10):1001–1012, 2016. Available at https://doi.org/10.4169/amer.math.monthly.123.10.1001.

[Nay23]Nayuki. Fast Fibonacci algorithms. Blog post at https://www.nayuki.io/page/fast-fibonacci-algorithms (permalink), January 2023.

[O’D21] Mike O’Donnell. The SKI combinator calculus: a universal formal system. Online course notes (permalink), May 2021. Accessed: 2025 08 16.

[Pro23]Liam Proven. War of the workstations: How the lowest bidders shaped today’s tech landscape. Online article at https://www.theregister.com/2023/12/25/the_war_of_the_workstations/ (permalink), December 2023.

[Sch11]Berry Schoenmakers. Σ-protocols. In Henk C. A. van Tilborg and Sushil Jajodia, editors, Encyclopedia of Cryptography and Security, pages 1206–1208. Springer US, Boston, MA, 2011. doi:10.1007/978-1-4419-5906-5_12.

[SW22]Abner J. Salgado and Steven M. Wise. Polynomial interpolation. In Classical Numerical Analysis: A Comprehensive Course, page 231–265. Cambridge University Press, 2022.

[Tar16]Paul Tarau. Computing with catalan families, generically. In Marco Gavanelli and John Reppy, editors, Practical Aspects of Declarative Languages, pages 117–134, Cham, 2016. Springer International Publishing.

[Tha22]Justin Thaler. Proofs, Arguments, and Zero-Knowledge. Number 4:2–4 in Foundations and Trends in Privacy and Security. Now publishers, December 2022. Available online at https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf (permalink).

[vD02]Dirk van Dalen. Intuitionistic logic. In D.M. Gabbay and F. Guenthner, editors, Handbook of Philosophical Logic, 2nd Edition, Volume 5, pages 1–114. Kluwer, 2002.

[Ver24]Rineke (L.C.) Verbrugge. Provability Logic. In Edward N. Zalta and Uri Nodelman, editors, The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University, Summer 2024 edition, 2024.

[Wik25]Wikipedia. General recursive function. http://en.wikipedia.org/w/index.php?title=General%20recursive%20function&oldid=1303228064, 2025. Accessed 16 August 2025.

Notes

aThis paper is published in the Journal of Applied Logics, Volume 12, number 6, pp 1481–1548, October 2025. College Publications, London ↩

1...and it would be impossible to even try, because progress in verifiable computation is currently so rapid. ↩

2Not an exclusive claim: cryptography also uses Boolean circuits. But what interests us here is the use of arithmetic ones. ↩

3A compact but clear overview is some online course notes [Cha25, Subsection 5.1] (direct link). ↩

4There are two distinct notions of ‘number’ in play here: integers, which relate to arithmetic circuits; and bitwise integers, which are a distinct thing and relate to Boolean circuits. ↩

5Of course, all programming languages do this to some extent (an XKCD comic strip (permalink) makes a pithy, and entertaining, comment on this), but MSP takes this abstraction to its logical (pun intended) extreme. Aside from the exceptionally high levels of abstraction, MSP is also characterised by something else: using specification languages based on mathematical logic and its semantics. ↩

6It is debatable whether the standard instruction-set based architectures that have evolved for efficiency on silicon are also an optimal compilation target in a world made out of polynomials. A remarkable article in The Register [Pro23] provides further context and is well worth reading (see the discussion of Dylan). See also an experience report [DMaN24, Section 6] on a (successful) use of functional programming in financial markets. ↩

7The Wikipedia page and this overview are excellent and very accessible introductions. ↩

8A tuple of rationals would do just as well, but we will only interpolate tuples of integers. ↩

9For example, 1-tuple (a) can be interpolated by a ∗X0, which is a zero degree polynomial. By convention, we interpolate the 0-tuple () with 0 and consider this to have degree −1. This edge case will not arise in our applications. ↩

10The reader might have seen this called composition or evaluation. I prefer instantiation because this is descriptive: X in P is a formal symbol and we instantiate it to Q. ↩

11Representing truth with 0 and non-truth with nonzero does have some pedigree. In a paper from 1943 [Kle43] on page 51 just after equation 17, Kleene writes “a representing function π of P, the value of which is to be 0, 1, or undefined according as the value of P is true, false, or undefined”. More recently, in the sysexists.h file (credited to Eric Allman in 1980) which describes status codes for system programs, 0 represents successful termination and nonzero values represent various kinds of failure. ↩

12A multivariate generalisation of the ideas in this paper is possible, and may be helpful for efficiency. However, in terms of expressivity just the one X will suffice for our needs. ↩

13In fact, it will turn out that pos is more interesting than one might expect. We will see more of it later in Subsection 4.1.1. ↩

14So if ϕ is a predicate and x ∈ℚ and ς is an interpretation then: ⟦ϕ⟧ς is a polynomial; ⟦ϕ⟧ς(x) is a rational number; and x ⊨ς ϕ is a truth-value. ↩

15This use of the word witness is consistent with the notion of witness to an existential quantification in logic. Our notion of validity ⊨ς ϕ is agnostic to where ϕ and ς come from, but in our intended application ϕ will be universally quantified (supplied by the validator) and ς will be existentially quantified (supplied by the prover). Or, to put things more abstractly: we intend validity judgements be used such that a validator fixes some desired property, and a prover constructs a witnessing model to that property, and proves that it has done so, without necessarily revealing the model to the validator. There is a subtle possibility for confusion here: in cryptography some details of the witness may be fixed by the validator, e.g. “Find me a model with at least 10 elements” or “Let the input to the program be 42”. Such is the power of logic, that this information can be adjoined to ϕ. ↩

16Obviously, in an implementation we care about efficiency so we might (or might not) prefer the rows of our matrix to be delivered as a vector of interpolating polynomials, along with an intended length. We can choose how best to represent our data. But, what that representation represents, is a matrix. ↩

17Indeed, the square is there precisely to guarantee nonnegativity. ↩

18Note that ⟦t⟧ς is just a number, because t is a term that is assumed to not mention X. ↩

19Pedant point: Calling ς(pow) an ‘interpretation’ might be a little misleading, so let us unpack the layers. ς is an interpretation, as per Definition 2.3.2(1). pow is a syntactic symbol which we call a matrix variable symbol. ς(pow) is the matrix value (a denotation) which the interpretation ς assigns to the syntactic matrix variable symbol pow. ↩

20For example, in classical logic P =⇒Q is equivalent to ¬P ∨Q. Constructively, P =⇒Q is a concrete method for turning a witness to the truth of P, into a witness to the truth of Q. ↩

21We consider how to check this using the Schwartz-Zippel lemma later, in Lemma 5.1.2. ↩

22It might be possible to efficiently ‘renormalise’ our polynomials to eliminate repeated roots, using formal derivatives and polynomial long division. Indeed, what really matters to us is not the degree of the polynomial itself, but how many distinct rational roots it has. But for now, just looking a the degree of the polynomial will suffice. ↩

23They are, but not in ways that matter to us here. ↩

24Well ...it depends on your point of view. They are recursive calls, but in a computation that is a verification of another computation that we assume has already been made. ↩

25An interpretation ς could contain repeated columns, corresponding to repeated calls to the same function on the same inputs, but this would be an inefficient prover; the verifier is still efficient on that (needlessly complex) input. Example 3.2.8 includes some basic examples with duplicated columns; they could be removed, but beyond padding out the matrix they do no harm. ↩

26Indeed, in the underlying silicon — in the low-level instructions that computer chips actually execute — 64-bit integers are typically the native notion of data. ↩

27This would leak a bit of information, but if all we are leaking is pointers then that might not matter, depending on the use case. ↩

28A quite clear treatment is available online [O’D21]. A compilation of λ-terms to SK combinator terms is at https://en.wikipedia.org/wiki/Combinatory_logic#Conversion_of_a_lambda_term_to_an_equivalent_combinatorial_term ↩

29One nice recent example is Nock: https://nock.is/intro.html. ↩

30Clear and accessible accounts of the Cantor pairing function are also on Wikipedia at https://en.wikipedia.org/wiki/Pairing_function#Cantor_pairing_function and https://en.wikipedia.org/wiki/Fueter%E2%80%93P%C3%B3lya_theorem. ↩

31By which we mean an injective map from the syntax of a language to natural numbers. Such maps are so called because Gödel used one such in his 1931 paper on incompleteness results. ↩

32Coinductive derivation systems (whose derivation-trees may be cyclic) do exist; but the evaluation relation for combinators is inductively defined. ↩

33So we can still say that our semantics is polynomial, even though t < Ci does not look like a polynomial expression: it evaluates to a number ⟦t < Ci⟧ς, and a number is trivially a polynomial. ↩

34Excluded middle is the property ‘ϕ-or-not-ϕ’, which when filtered through our polynomial semantics from Figure 2 renders as a ∗ neg(a) = 0. ↩

35This corresponds to ‘ϕ-and-not-ϕ’, which we expect to be false, i.e. nonzero. ↩

36This would not be solved by switching to a finite field. In practical terms, any finite field large enough to be cryptographically secure is also large enough to be practically unenumerable. This is why cryptographic assurances work! Thus, modelling ‘true’ by a single value and ‘false’ by many values is not a bug of our semantics. Far from it; it reflects an essential feature of the cryptographic notion of proof. ↩

37In a finite field with n elements, this would require a polynomial of degree n. In an infinite field, it is impossible. ↩

38‘Innermost’ means that t does not itself contain some subterm of the form f(t′). ↩

39Tall but narrow matrices are cheap; see Remark 6.2.1(2). Thus, a transformation that increases arity (and thus the height of matrices) but does not affect their width, is free, to a first approximation. ↩

40This implementation is not necessarily optimal, but it is simple. ↩

41The Wikipedia page [Wik25] gives a clear and accessible presentation. ↩

42We started counting at 1 in the first argument for the technical reason that we will be most interested in applying this to identify columns in matrices, which we count from 1, not 0. There is no deeper mathematical significance here. ↩

43...or undefined. ↩

44An initial segment I ⊆ℕ≥1 is such that if a ∈I and a > 1 then a − 1 ∈I. Note that ∅⊆ℕ≥1 is initial. ↩

45We impose this condition explicitly in Figure 10 as nand.in1(X) = 0 ∨ nand.in1(X) = 1 and similarly for nand.in2; however, we could also insist on 0 ≤ nand.in1 ≤ 1. Because an interpretation ς returns an integer matrix, this would suffice. These two methods are however subtly different: if we care about zero knowledge then it may be that range checked values get exposed to the validator. See point 2 of the discussion in Subsection 5.2. ↩

46Note that in this system wires can be duplicated; the output of a gate can be wired to zero, one, or many outputs. ↩

47The Schwartz-Zippel lemma is actually a more general statement about multivariate polynomials over integral domains. Lemma 5.1.1 is the special case of a univariate polynomial over ℚ. Even so, what is written captures the spirit and character of the general result. ↩

48We can quantify this with some concrete numbers. A reasonable value for d is 109 (a gigabyte is roughly 109 bytes), and in one commercial system https://docs.starkware.co/starkex/crypto/stark-curve.html (permalink) 𝔽 is finite with size roughly 2251 so we can just set S = 𝔽. Then we can compute 2251/109 ≈ 4 ∗ 1066. For comparison, there are only about 1057 protons and neutrons in the solar system. ↩

49Let’s make this concrete by listing some misconceptions about logic that I have encountered. Misconception: ‘Computation’ means ‘execution of a Turing machine’. Thus if it doesn’t run on a virtual machine (with memory and a program counter etc), it’s not computation. As a further corollary, all data is token strings (not ‘representable as’; is). Misconception: λ-calculus, logic programming, and denotational semantics do not exist. Misconception: Derivation-trees. Is this an execution trace? Why does it branch; is it non-deterministic? What virtual machine does it execute on? Misconception: Logic is undecidable. Thus every predicate is undecidable and logic cannot be used to say anything useful in practice. Misconception: Logic is not Turing-complete and thus cannot be used to specify computation. Misconception: Induction makes no sense, since the inductive hypothesis assumes what you want to prove. Misconception: Logic is nice, but it has many predicates and they are all different. Is there a uniform language to specify things? (The person is asking for a programming language.) Misconception: ‘Prove’ means ‘test’, as in ‘unit test’. ‘Logic’ means ‘rules’, as in ‘business logic’. Misconception: Algorithms are only thing that really matters. Programming is just connecting algorithms together in the right order, which should be straightforward. Misconception: The only assertion relevant to programming is ‘computation has been executed according to the rules of the virtual machine’. Furthermore, if this is shown then it means the program is correct. The list goes on. All this is to note that barriers to practical realisation of verifiable computation via a shallow compositional embedding of logic in polynomials, are cultural and educational, not just technical and mathematical. Even if the mathematics in this paper were perfect and sufficient (and it’s not), even that alone would not suffice. Pro tip: don’t say you have a ‘logic’; say ‘framework’ instead. ↩

50Let’s read that out: if x is a root of ⟦ϕ⟧ς for every ϕ ∈ Φ then it is a root of ⟦ψ⟧ς. ↩

51See also Remark 3.2.12 which comments on the efficiencies of being able to remove repeated roots. ↩

52This is not a Gödel encoding! A Gödel encoding would inject raw predicate syntax into numbers. reify behaves more like a type casing function, mapping predicate semantics into term semantics — as a no-op, since both are just polynomials. ↩

53Note that this would require us to think about how to represent the syntax of FOL propositions and the syntax of FOL derivation-trees, in polynomials. This is possible but it’s just an extra layer of complexity. We can turn this around: the relative straightforwardness of the representation in this paper is a feature, not a bug, and it is no accident but the result of specific design decisions. Of course we hope there will be scope to make things even simpler and more direct, and if so this is future work. ↩

54Correct by construction with respect to the specification. If the specification is buggy then the program constructed from it will be too. But it will faithfully satisfy the (incorrect) specification. ↩

55This seems to be a point of confusion, so I will repeat it: a big computation trace does not necessarily mean that the notion of validity of that trace is particularly complex. Furthermore, the validity predicate ϕ only needs to be compiled to a polynomial once, and then we can check validity of as many interpretations that claim to validate ϕ, as we like. ↩