Characterization of robust immune symmetric boolean functions

Abstract

Fix a field $\mathbb {F}$. The algebraic immunity over $\mathbb {F}$ of boolean function f : {0, 1}ⁿ → {0, 1} is defined as the minimal degree of a nontrivial (multilinear) polynomial $g(x) \in \mathbb {F}[x_{1}, \ldots , x_{n}]$ such that f(x) is a constant (either 0 or 1) for all x ∈ {0, 1}ⁿ satisfying g(x) = 0. Function f is called k r o b u s t i m m u n e if the algebraic immunity of f is always not less than k no matter how one changes the value of f(x) for k ≤ |x| ≤ n − k. For any field $\mathbb {F}$, any integers n, k ≥ 0, we characterize all k robust immune symmetric boolean functions in n variables. The proof is based on a known symmetrization technique and constructing a partition of nonnegative integers satisfying certain (in)equalities about p-adic distance, where p is the characteristic of the field $\mathbb {F}$.

1 Introduction

In cryptography community, algebraic immunity (over $\mathbb {F}_{2}$) is proposed as a criteria for boolean functions used in some stream ciphers to resist algebraic attacks [6]. In order to resist algebraic attacks (as well as many others), there are a lot of constructions aiming to achieve high algebraic immunity, high nonlinearity, balancedness, and so on [4, 5, 12, 15].

Symmetric boolean functions are those whose output is invariant under permutations of inputs. Regardless of its application in stream cipher, symmetric boolean functions are particularly well studied due to its relatively simple structure. It turns out all symmetric boolean functions with maximum algebraic immunity ⌈n/2⌉ can be completely characterized, cumulated along a line of research [2, 10, 11, 13, 14, 16], etc.

In computational complexity, algebraic immunity (the same definition under different names!) also attracts some attention. Namely, (one-sided) immunity of f is defined as the minimal degree of a nontrivial polynomial g such that f(x) = 0 ⇒ g(x) = 0; immunity over $\mathbb {F}_{p}$ is also called weak mod-p degree. In circuit complexity, roughly speaking, lower bound on the algebraic immunity will imply circuit lower bound under various models [3, 7–9]. In proof complexity, immunity plus some expanding property implies degree lower bounds for Polynomial Calculus [1].

This work is motivated by the goal to characterize all symmetric boolean functions with any given algebraic immunity (not only maximum). To make the problem easier, we propose the definition of k robust immune (which is stronger than algebraic immunity), and end up with a complete characterization of k robust immune symmetric boolean function for any k over any field $\mathbb {F}$. The the first ingredient is a known symmetrization technique which has been successfully applied to understand algebraic immunity of symmetric Boolean functions. The main technical part is a construction of the (unique) partition of nonnegative integers which satisfies certain p-adic distance (in)equalities, which will imply a complete list of robust immune symmetric boolean functions.

2 Main result

Definition 1

Let $\mathbb {F}$ be a field, and f : {0, 1}ⁿ → {0, 1} be a boolean function. The algebraic immunity of f over field $\mathbb {F}$ is defined as the minimal degree of a nontrivial¹ polynomial $g \in \mathbb {F}[x_{1}, \ldots , x_{n}]$, such that f becomes a constant when restricting to the zeros of g, i.e., there exists some c ∈ {0, 1} such that g(x) = 0 ⇒ f(x) = c.

In cryptography community, algebraic immunity usually refers to that over $\mathbb {F}_{2}$, and can also be defined as the minimal $\mathbb {F}_{2}$-degree of some boolean function g such that f g = 0² or (1 − f)g = 0. If f g = 0, then g is called an annihilator of f (over boolean cube). In words, algebraic immunity of f is the smallest degree of some nonzero annihilator of either f or 1 − f.

Definition 2

Boolean function f : {0, 1}ⁿ → {0, 1} is called k robust immune over field $\mathbb {F}$ if the algebraic immunity of f over $\mathbb {F}$ is always not less than k no matter how one changes the values of f(x) with k ≤ |x| ≤ n − k, where |x|:=x ₁+…+x _n is the weight of x.

The definition of k robust immune looks a bit artificial. However, the reason why we allow changing values of f(x) for k ≤ |x| ≤ n − k instead of k′ ≤ |x| ≤ n − k′ for some other k′ is because k′=k is the largest possible integer to take. Another reason we propose this definition is because we are able to characterize all k robust immune symmetric boolean functions, while the goal keeping in mind is to give such a characterization for all symmetric boolean functions with any given algebraic immunity.

Our main result is the following characterization of all k robust immune symmetric boolean functions for any given k over any field $\mathbb {F}$. For convenience, if f : {0, 1}ⁿ → {0, 1} is symmetric, let v _f :{0, 1,…,n} → {0, 1} be its value vector, that is, f(x) = v _f (|x|).

Theorem 1

For any field $\mathbb {F}$, any integer t ≥ 0, there exists a partition $\mathcal {P} = \mathcal {P}(\mathbb {F}, t)$ of nonnegative integers such that, for any k, symmetric boolean function f : {0, 1}^{2k + t−1} → {0, 1} is k robust immune if and only if

$$ v_{f}(k - 1 - i) = 1 - v_{f}(k + t + j) $$

(1)

for any 0 ≤ i, j ≤ k − 1 belonging to the same set in partition $\mathcal {P}$.

Remark 1

The partition $\mathcal {P} = \mathcal {P}(\mathbb {F}, t)$ will be defined explicitly in the following sequel, and $\mathcal {P}$ only depends on t and the characteristic of the field $\mathbb {F}$, which follows from the following linear algebra argument. Function f has no degree ≤d annhilator if and only if some matrix of size ${n \choose \le d} \times |f^{-1}(1)|$ has rank ${n \choose \le d}$, which is a {0, 1}-matrix³. It is clear that the rank of the {0, 1}-matrix does not change over any field extension.

Remark 2

It is known that the algebraic immunity of any n-variable boolean function is upper bounded by ⌈n/2⌉, which is not difficult to see by a dimension argument. When t = 0, f is an odd-variable symmetric boolean functions with maximum algebraic immunity; and when t = 1, f is an even-variable symmetric boolean function with maximum algebraic immunity.⁴ For the case $\mathbb {F}= \mathbb {F}_{2}$ and t = 0,1, our theorem is implicitly known [11, 16]. For general field $\mathbb {F}$ and general t, our result is a nontrivial generalization.

3 Overview of the proof

The proof follows from a crucial symmetrization technique in [10] and the calculation of a determinant over the field $\mathbb {F}_{p}$. It turns out the symmetric boolean function is k robust immune if and only if some corresponding matrices have full rank, that is, the determinant is nonzero. Over the field $\mathbb {F}_{p}$, in order to prove the determinant is nonzero, the calculation involves a lot of p-adic distance estimates.

The following lemma says in order to prove symmetric boolean function f has no nonzero annihilator of certain degree, it suffices to consider the semi-symmetric annihilators up to that degree. The crucial lemma is proved by Liu and Feng in [10] for $\mathbb {F} = \mathbb {F}_{2}$, and observed in [3] that it works for any field.

Lemma 1

[ 10 ] Let $\mathbb {F}$ be a field, and f : {0, 1}ⁿ → {0, 1} be a symmetric boolean function. Then f has a lowest degree annihilator g of the following form,

$$g = \prod\limits_{i = 1}^{l} (x_{2i-1} - x_{2i})g^{\prime}, $$

where g′ is a symmetric function in variables x _{2l +1},…,x _n .

For convenience, let us introduce the following notation $\psi _{k} : \mathbb {Z}_{\ge 0} \to \mathbb {F}^{k}$, where

$$\psi_{k}(x) = \left( {x \choose 0}, {x \choose 1}, \ldots, {x \choose k-1} \right) \in \mathbb{F}^{k}, $$

where ${x \choose i} = \underbrace {1 + 1 + {\ldots } + 1}_{{x \choose i} \, \text { times}}$. In other words, ${x \choose i} = {x \choose i} \pmod p$ over field $\mathbb {F}_{p}$. The following proposition is an immediate consequence of Lemma 1.

Proposition 1

Let f : {0, 1}ⁿ → {0, 1} be a symmetric boolean function, and v _f : {0, 1,…,n} → {0, 1} be its corresponding value vector. Function f is k robust immune if and only if, for any 0 ≤ l ≤ k − 1, both

$$ \{ \psi_{k - l}(i-l) : i \in [l, k-1]\cup[n-k+1,n-l] \,\,\text{ and} \,\, v_{f}(i) = 0 \} $$

(2)

and

$$ \{ \psi_{k - l}(i-l) : i \in [l, k-1]\cup[n-k+1,n-l] \,\,\text{ and} \,\, v_{f}(i) = 1 \} $$

(3)

are bases of $\mathbb {F}^{k-l}$.

Proof

By the definition of k robust immune, for symmetric boolean function f, it suffices to prove f ₀ has no annihilator of degree < k, and 1 − f ₁ has no annihilator of degree < k, where

$$v_{f_{0}}(x) = \left\{ \begin{array}{ll} v_{f}(x) & \,\, x \in [0, k-1]\cup [n-k+1, n]\\ 0 & \,\, \text{otherwise} \end{array} \right. $$

and

$$v_{f_{1}}(x) = \left\{ \begin{array}{ll} v_{f}(x) & \,\, x \in [0, k-1]\cup [n-k+1, n]\\ 1 & \,\, \text{otherwise}. \end{array} \right. $$

By Lemma 1, f ₀ (the argument for f ₁ is similar) has no annihilator of degree < k if and only if it has no annihilator of the form $g = {\prod }_{i = 1}^{l} (x_{2i-1} - x_{2i})g^{\prime },$ where g′ is a symmetric function in x _2l+1,…,x _n of degree < k − l. Fix some 0 ≤ l ≤ k − 1. $f_{0} g = 0 \Leftrightarrow f_{0} {\prod }_{i=1}^{l} (x_{2i-1} - x_{2i})g^{\prime } = 0$, which is equivalent to $f_{0}^{\prime } g^{\prime } = 0$, where

$$f_{0}^{\prime} = f_{0}|_{x_{1} = x_{3} = {\ldots} = x_{2l-1} = 1, x_{2} = x_{4} = {\ldots} = x_{2l} = 0}. $$

It is easily checked that $v_{f_{0}^{\prime }} = (v_{f_{0}}(l), v_{f_{0}}(l+1), \ldots , v_{f_{0}}(n - l))$. Note that both $f_{0}^{\prime }$ and g′ are symmetric, and deg(g)< k − l. Thus we may write

$$g^{\prime} = a_{0} e_{0} + {\ldots} + a_{k-l-1} e_{k-l-1}, $$

where e _i is the elementary symmetric polynomial of degree i, which takes value ${x \choose i}$ at any point with weight i. The condition $f_{0}^{\prime } g^{\prime } = 0$ is equivalent to g′(x) = 0 for all $v_{f_{0}^{\prime }}(x) = 1$, i.e., $a_{0} {x \choose 0} + a_{1} {x \choose 1} + {\ldots } + a_{k-l-1} {x \choose k-l-1} = 0$. Therefore, such g′ exists if and only if there exists a nonzero $a \in \mathbb {F}^{k-l}$ such that a ^T ψ _{k − l} (x) = 0 for all $v_{f_{0}^{\prime }}(x) = v_{f}(x + l) = 1$, that is, {ψ _{k − l} (i − l):i ∈ [l, k − 1]∪[n − k+1,n − l] and v _f (i) = 1} has rank < k − l. □

Remark 3

From the above proposition, we can see if symmetric f is k robust immune, then v _f (i) = 1 − v _f (n − i) for 0 ≤ i ≤ k − 1, and $f|_{x_{1} = 1, x_{2} = 0}$ is k − 1 robust immune.

Next step is to notice ψ _k (x ₀),ψ _k (x ₁),…,ψ _k (x _{k − 1}) has full rank if and only if the determinant is nonzero (over the field $\mathbb {F}$), where the determinant turns out to have the following simple form [3]⁵

$$ \det(\psi_{k}(x_{0}), \psi_{k}(x_{1}), \ldots, \psi_{k}(x_{k-1})) = \prod\limits_{0 \le i < j \le k - 1} \frac{x_{j} - x_{i}}{j - i}. $$

(4)

Over the the field $\mathbb {F}$ with characteristic 0, the above determinant is always nonzero for distinct x ₀,…,x _{k − 1}, which implies $\mathcal {P}(\mathbb {F}, t) = \{ \{0\}, \{1\}, \{2\}, \ldots \}$ for any t ≥ 0; over field with characteristic p, the determinant is nonzero if and only if

$$ \sum\limits_{0 \le i < j \le k -1}\text{ord}_{p}(x_{j} - x_{i}) = \sum\limits_{0 \le i < j \le k -1} \text{ord}_{p}(j - i), $$

(5)

where ord _p (x) is the p-adic order of x, that is, the maximum integer m such that p ^m divides x. From now on, we will assume $\mathbb {F} = \mathbb {F}_{p}$ for some prime p.

Combining (4) with Proposition 1, we have the following lemma, which says if the partition $\mathcal {P}$ satisfies certain condition, then the functions in Theorem 1 are k robust immune.

Lemma 2 (Sufficiency)

Fix some integer t ≥ 0 and k > 0. Let $\mathcal {P}$ be a partition of {0,…,k − 1}, i.e., $\mathcal {P} = \{I_{0}, I_{1}, \ldots \}$ , where $\dot \cup _{i \ge 0} I_{i} = \{0, \ldots , k - 1\}$ . If for all $I \in \mathcal {P}$ , we have

$$ \sum\limits_{x \in I \,\,\textit{and}\,\, x < y} \text{ord}_{p}(y - x) = \sum\limits_{x \in I \,\,\textit{and}\,\, x < y} \text{ord}_{p}(y+x+t+1) $$

(6)

for all 0 ≤ y ≤ k − 1 with y ∉ I, then all symmetric boolean functions satisfying (1) are k robust immune.

Proof

By Proposition 1, it suffices to prove that for all l, both (2) and (3) are bases of $\mathbb {F}^{k-l}$. With loss of generality, assume l = 0, and we shall prove (2) is a basis of $\mathbb {F}^{k}$.

By condition (1), we know that, there exists index set S such that

$$\{ k - 1 - i : v_{f}(i) = 0 \,\,\text{and} \,\, i \in [0,k-1]\} = \bigcup\limits_{i \in S} I_{i}, $$

and

$$\{ i - k - t : v_{f}(i) = 0 \,\,\text{and} \,\, i \in [k+t,2k+t-1]\} = \bigcup\limits_{i \not\in S} I_{i}, $$

where $\mathcal {P} = \dot \cup _{i} I_{i}$. By (5), it suffices to prove

$$\sum\limits_{0 \le i < j \le k - 1} \text{ord}_{p}(j - i) = \sum\limits_{0 \le i < j \le k - 1} \text{ord}_{p}(x_{j} - x_{i}), $$

where x _j is either k − 1 − j or k + t + j, depending on whether j ∈ ∪ _{i ∈ S} I _i or not.

$$\begin{array}{@{}rcl@{}} && \sum\limits_{0 \le i < j \le k - 1} \text{ ord}_{p}(x_{j} - x_{i}) \\ && = \sum\limits_{i < j \atop i, j \in S \,\text{ or} \, i, j \not\in S} \text{ord}_{p}(j - i) + \sum\limits_{i < j \atop i \in S, j \not\in S \,\text{ or} \, i\not\in S, j \in S} \text{ord}_{p}(j+i+t+1) \\ && = \sum\limits_{i < j \atop i, j \in S \,\text{ or} \, i, j \not\in S} \text{ord}_{p}(j - i) + \sum\limits_{i < j \atop i \in S, j \not\in S \,\text{ or} \, i\not\in S, j \in S} \text{ord}_{p}(j - i) \\ && = \sum\limits_{0 \le i < j \le k - 1} \text{ord}_{p}(j - i), \end{array} $$

where the second last step follows from our condition (6). □

Lemma 3 (Necessity)

Fix some integer t ≥ 0 and k > 0. Let $\mathcal {P}$ be a partition of {0,…,k − 1} satisfying (6) in Lemma 2. If for any $y \in I \in \mathcal {P}$ with {x ∈ I : x < y} nonempty,

$$ \sum\limits_{x \in I \,\,\textit{and}\,\, x < y} \text{ord}_{p}(y - x) < \sum\limits_{x \in I \,\,\textit{and}\,\, x < y} \text{ord}_{p}(y+x+t+1), $$

(7)

then all k robust immune symmetric boolean functions satisfy (1).

Proof

Let $\mathcal {P}$ be a partition of {0,1,…,k − 1} satisfying the conditions in this lemma. Assume for contradiction that there exists some k robust immune symmetric boolean function which does not satisfy (1).

Let 0 ≤ i< j ≤ k − 1 be some pair which violates (1) with minimum j. Let l = k − 1 − j, and we shall prove

$$ \{ \psi_{k - l}(i-l) : i \in [l, k-1]\cup[n-k+1,n-l] \,\,\text{ and} \,\, v_{f}(i) = 0 \} $$

(8)

is not a basis of $\mathbb {F}^{k-l}$, which would be a contradiction to Proposition 1.

Let $\mathcal {P} \cap \{0, 1, \ldots , k-l-1\} = \{I_{0}, I_{1}, \ldots , I_{m}\}$, which is the partition of {0, 1,…, k − l − 1} induced by $\mathcal {P}$. Without loss of generality, assume j ∈ I _m . Then the set (8) is exactly the union of

$$\{ \psi_{k-l}(k-1-x-l) : x \in I_{0}\} \,\,\text{ or} \,\, \{\psi_{k- l}(k+t+x-l) : x \in I_{0} \} \\ $$

$$\{ \psi_{k-l}(k-1-x-l) : x \in I_{1}\} \,\,\text{ or} \,\, \{\psi_{k-l}(k+t+x-l) : x \in I_{1} \} \\ $$

$$\vdots $$

$$\{ \psi_{k-l}(k-1-x-l) : x \in I_{m-1}\} \,\,\text{ or} \,\, \{\psi_{k-l}(k+t+x-l) : x \in I_{m-1} \} \\ $$

$$\{ \psi_{k-l}(k-1-x-l) : x \in I_{m} \setminus\{j\}\}\cup\{\psi_{k-l}(k+t+j-l)\} $$

$$\,\,\text{ or} \,\, \{\psi_{k-l}(k+t+x-l) : x \in I_{m} \setminus \{j\} \}\cup\{\psi_{k-l}(k-1-j-l)\}. \\ $$

Following the same calculation as we did in Lemma 2, we claim that the order of the determinant is exactly

$$\sum\limits_{x \in I_{m} \,\,\text{and}\,\, x < y} \text{ord}_{p}(y+x+t+1) - \sum\limits_{x \in I_{m} \,\,\text{and}\,\, x < y} \text{ord}_{p}(y - x), $$

which is greater than 0 by our condition in the lemma, and thus the determinant over $\mathbb {F}_{p}$ is zero, and therefore (8) is not a basis. □

Given field $\mathbb {F}$, integer t, k, assuming there exists a partition $\mathcal {P}$ of {0, 1,…, k − 1} satisfying (6) and (7), then by Lemma 2 and Lemma 3, we will obtain all k robust immune symmetric boolean functions in 2k + t − 1 variables. It remains to prove the existence of such partitions, and we will construct $\mathcal {P}$ inductively on t. An interesting feature, which in fact follows from (6) and (7), is that $\mathcal {P}$ does not depend on k, that is to say, $\mathcal {P}(\mathbb {F}, t, k)$ and $\mathcal {P}(\mathbb {F}, t, k+1)$ induce the same equivalence relation on {0, 1,…, k − 1}. Let us summarize the conditions we need on $\mathcal {P}(\mathbb {F}_{p}, t)$, which is our main technical lemma.

Lemma 4 (Main technical lemma)

For any prime p, and any integer t ≥ 0, there exists a partition $\mathcal {P} = \mathcal {P}(\mathbb {F}_{p}, t)$ of nonnegative integers satisfying the followings.

• (Soundness) For all $I \in \mathcal {P}$, y ∉ I, we have

  $$ \sum\limits_{x \in I \,\,\textit{and}\,\, x < y} \text{ord}_{p}(y - x) = \sum\limits_{x \in I \,\,\textit{and}\,\, x < y} \text{ord}_{p}(y+x+t+1). $$

  (9)

• (Completeness) For any $y \in I \in \mathcal {P}$ with {x ∈ I : x < y} nonempty,

  $$ \sum\limits_{x \in I \,\,\textit{and}\,\, x < y} \text{ord}_{p}(y - x) < \sum\limits_{x \in I \,\,\textit{and}\,\, x < y} \text{ord}_{p}(y+x+t+1). $$

  (10)

Putting everything together, it is easy to see Lemma 4 together with Lemma 2 and Lemma 2 implies our main theorem. All the remaining pages are devoted to the constructive proof of Lemma 4, which is a bit tedious. It would be interesting to find a simpler proof of Lemma 4, probably an existential proof.

4 Proof for the case $\text {char}(\mathbb {F}) = 2$

In this section, we will prove Lemma 4 for $\mathbb {F} = \mathbb {F}_{2}$.

Notations

We are introducing some handy notations, which are nonstandard but will be convenient and intuitive for the following proofs. For p = 2 (or any prime p ≥ 2), integer x ≥ 0 has a unique p-adic expansion⁶

$$x = (x_{0}, x_{1}, x_{2}, \ldots)_{2}, $$

where $x = {\sum }_{i \ge 0} x_{i} 2^{i}$. When there is no ambiguity, we will drop the subscript 2 . A pattern, either denoted by an p-adic expansion or Greek alphabets α, β, is subset of $\mathbb {Z}_{\ge 0}$ descried by p-adic expansion by the following rules.

• Character ∗ denotes any 01-string of arbitrary length, that is, pattern (∗) is exactly $\mathbb {Z}_{\ge 0}$.

• Character ? denotes a single bit, i.e., either 0 or 1. For example, (?,0,∗) denotes the set of nonnegative integers congruent to 0,1 mod 4.

• An integer superscript i means repeating i times. For example, (0ⁱ,∗) denotes the set of nonnegative integers which are multiples of 2ⁱ.

• If α is a pattern, it can be put at the end of p-adic expansion to define a new pattern, like (0,0,α), which is the set of integers 4x, x ∈ α.

• Since patterns are sets, set operations can be applied. For example, α∩[0,y] is {x ∈ α : x ≤ y}.

We are ready to define partition $\mathcal {P}(\mathbb {F}_{2}, t)$. Within this section, we may simply write $\mathcal {P}(\mathbb {F}_{2}, t)$ as $\mathcal {P}(t)$.

Definition 3

Let $\mathcal {P}(0) = \{ (*) \} \,\,\text { and} \,\, \mathcal {P}(1) = \{ (1^{i}, 0, *) : i = 0, 1, {\ldots } \}.$ For integer t ≥ 1,

$$\mathcal{P}(2t) = \{ (?, \alpha) : \alpha \in \mathcal{P}(t) \}. $$

For odd integer t ≥ 1,

$$\mathcal{P}(2t+1) = \{ (0, 0, \alpha) : (0, \alpha) \in \mathcal{P}(t) \} \cup \{ (1,?,\alpha), (0,1,\alpha) : (1, \alpha) \in \mathcal{P}(t)\}. $$

For odd integer t ≥ 1 and e ≥ 2,

$$\mathcal{P}(2^{e}t+1) = \{ (1^{e}, \alpha) : \alpha \in \mathcal{P}(t+1)\} \cup \{ (1^{i}, 0, ?^{e-1-i}, \alpha) : \alpha \in \mathcal{P}(t), 0 \le i \le e-1 \}. $$

It is not difficult to see $\mathcal {P}(t)$ is well-defined, that is, it is a partition of $\mathbb {Z}_{\ge 0}$. To make sure the readers understand our definition of $\mathcal {P}(t)$, let us restate the the definition in standard set notations.

$$\begin{array}{@{}rcl@{}} \mathcal{P}(0) & = & \{ \mathbb{Z}_{\ge 0} \}. \\ \mathcal{P}(1) & = & \{ 2^{r+1} \mathbb{Z}_{\ge 0} + 2^{r}-1 : r = 0, 1, {\ldots} \}.\\ \mathcal{P}(2t) & = & \{ 2I \cup (2I+1) : I \in \mathcal{P}(t) \}.\\ \mathcal{P}(2t+1) & = & \{ 2I : I \in \mathcal{P}(t) \,\,\text{ and} \,\, I \subseteq 2 \mathbb{Z}_{\ge 0} \} \cup \\ & & \{ 2I, (2I+1) \cup (2I-1) : I \in \mathcal{P}(t) \,\,\text{ and} \,\, I \subseteq 2 \mathbb{Z}_{\ge 0} + 1 \}. \\ \mathcal{P}(2^{e}t+1) & = & \{ 2^{e} I + 2^{e}-1 : I \in \mathcal{P}(t+1)\} \cup \\ & & \{ \bigcup\limits_{0 \le j \le 2^{e-1-i}-1} 2^{e} I + 2^{i+1} j + 2^{i}-1 : I \in \mathcal{P}(t), 0 \le i \le e-1 \}. \end{array} $$

In the following subsections, we will prove Lemma 4 for p = 2 by induction on t. According to our definition of $\mathcal {P}(t)$, the proof consists of 5 cases, that is, 0, 1, 2t, 2t + 1, 2^e t + 1.

4.1 $\mathcal {P}(\mathbb {F}_{2}, 0)$

Recall that $\mathcal {P}(0) = \{ \mathbb {Z}_{\ge 0} \}$. Soundness is trivially true. For completeness, we need to prove

$$ \sum\limits_{0 \le x < y} \text{ord}_{2}(y-x) < \sum\limits_{0 \le x < y} \text{ord}_{2}(y+x+1) $$

(11)

for any x > 0, which is equivalent to ord₂(y!) < ord₂((2y)!/y!), which is true because ${ 2y \choose y} \equiv 0 \pmod 2$ for any y > 0. We leave it as an exercise for readers, and (11) will be used again.

4.2 $\mathcal {P}(\mathbb {F}_{2}, 1)$

Recall that $\mathcal {P}(1) = \{ (1^{i}, 0, *) : i = 0, 1, {\ldots } \}.$ For soundness, let x ∈ (1ⁱ, 0, ∗) and y ∈ (1^j, 0, ∗), where i ≠ j. It is easily checked that ord₂(x − y) = ord₂(x + y + 2)= min(i, j), which proves the soundness.

For completeness, let y ∈ I = (1ⁱ, 0, ∗) with I ∩ [0, y − 1] nonempty, and we shall prove

$$\sum\limits_{x \in I\cap [0,y-1]} \text{ord}_{2}(y - x) < \sum\limits_{x \in I\cap [0,y-1]} \text{ord}_{2}(y + x + 2). $$

Let y = (y ₀ = 1,…,y _{i − 1} = 1,y _i = 0, y _{≥ i + 1}), where y _{≥ i + 1} denotes the integer (y _{i + 1}, y _{i + 2},…), that is, ${\sum }_{j \ge 0} 2^{j} y_{i+j+1}$. Adopt the same notation for x. It is easily checked that

$$\text{ord}_{2}(y - x) = i+1 + \text{ord}_{2}(y_{\ge i+1} - x_{\ge i+1}) $$

and

$$\text{ord}_{2}(y + x + 2) = i+1 + \text{ord}_{2}(y_{\ge i+1} + x_{\ge i+1} + 1). $$

Thus, it is equivalent to prove⁷

$$\sum\limits_{0 \le x_{\ge i+1} < y_{\ge i+1}} \text{ord}_{2}(y_{\ge i + 1} - x_{\ge i+1}) < \sum\limits_{0 \le x_{\ge i+1} < y_{\ge i+1}} \text{ord}_{2}(y_{\ge i + 1} + x_{\ge i+1} + 1) $$

for any y _{≥ i + 1} > 0 (by assumption {x ∈ I : x< y} is nonempty), which is exactly (11).

4.3 $\mathcal {P}(\mathbb {F}_{2}, 2t)$

By definition, $\mathcal {P}(2t) = \{ (?, \alpha ) : \alpha \in \mathcal {P}(t) \}$.

Soundness

Need to prove for any $y \not \in I \in \mathcal {P}(2t)$

$$ \sum\limits_{x \in I \cap [0,y-1]} \text{ord}_{2}(y - x) = \sum\limits_{x \in I \cap [0,y-1]} \text{ord}_{2}(y+x+2t+1). $$

(12)

Let I = (?,α), where $\alpha \in \mathcal {P}(t)$. Let y = (y ₀, y ₁,…), where y _≥1 ∉ α by assumption y ∉ I. The left hand side of (12) is

$$\begin{array}{@{}rcl@{}} && \sum\limits_{x \in I \cap [0, y-1]} \text{ord}_{2}(y - x) \\ && = \sum\limits_{x_{\ge 1} \cap [0, y_{\ge 1}-1]} \text{ord}_{2}((y_{0},y_{\ge 1}) - (y_{0}, x_{\ge 1})) \\ && = |\alpha \cap [0, y_{\ge 1}-1]| + \sum\limits_{x_{\ge 1} \cap [0, y_{\ge 1}-1]} \text{ord}_{2}(y_{\ge 1} - x_{\ge 1}). \end{array} $$

The right hand side of (12) is

$$\begin{array}{@{}rcl@{}} & & \sum\limits_{x \in I \cap [0,y-1]} \text{ord}_{2}(y + x + 2t+1 ) \\ && = \sum\limits_{x_{\ge 1} \in \alpha \cap [0, y_{\ge 1}-1]} \text{ord}_{2}((y_{0}, y_{\ge 1}) + (1 - y_{0}, x_{\ge 1}) + (1, t))\\ && = |\alpha \cap [0, y_{\ge 1}-1]| + \sum\limits_{x_{\ge 1} \in \alpha \cap [0, y_{\ge 1}-1]} \text{ord}_{2}(y_{\ge 1} + x_{\ge 1} + t + 1). \end{array} $$

By induction hypothesis, $\mathcal {P}(t)$ is sound, and thus ${\sum }_{x_{\ge 1}} \text {ord}_{2}(y_{\ge 1} + x_{\ge 1} + t + 1) = {\sum }_{x_{\ge 1}} \text {ord}_{2}(y_{\ge 1} - x_{\ge 1})$, which proves (12).

Completeness

We shall prove, for any $y \in I \in \mathcal {P}$ with {x ∈ I : x< y} nonempty,

$$ \sum\limits_{x \in I \cap [0, y-1]} \text{ord}_{2}(y - x) < \sum\limits_{x \in I \cap [0,y-1]} \text{ord}_{2}(y+x+t+1). $$

(13)

Let I = (?,α), where $\alpha \in \mathcal {P}(t)$. The left hand side of (13) is $|\alpha \cap [0, y_{\ge 1}-1] | + {\sum }_{x_{\ge 1} < y_{\ge 1}}\text {ord}_{2}(y_{\ge 1} - x_{\ge 1})$, while the right hand side is at least

$$|\alpha \cap [0, y_{\ge 1} - 1 ]| + \sum\limits_{x_{\ge 1} < y_{\ge 1}}\text{ord}_{2}(y_{\ge 1} + x_{\ge 1} + t + 1) + \delta_{y_{0}, 1}, $$

where $\delta _{y_{0}, 1} = 1$ if y ₀ = 1, otherwise 0. If α ∩ [0, y _≥1 − 1] is nonempty, we have ${\sum }_{x_{\ge 1} < y_{\ge 1}}\text {ord}_{2}(y_{\ge 1} + x_{\ge 1} + t + 1) > {\sum }_{x_{\ge 1} < y_{\ge 1}}\text {ord}_{2}(y_{\ge 1} - x_{\ge 1})$ by the completeness of $\mathcal {P}(t)$, which implies (13); otherwise y ₀ = 1, which also implies (13).

4.4 $\mathcal {P}(\mathbb {F}_{2}, 2t+1)$, t odd

Recall the definition, $\mathcal {P}(2t+1) = \{ (0, 0, \alpha ) : (0, \alpha ) \in \mathcal {P}(t) \} \cup \{ (1,?,\alpha ), (0,1,\alpha ) : (1, \alpha ) \in \mathcal {P}(t)\},$ where all patterns in $\mathcal {P}(t)$ are of the form (0, α) or (1,α) by definition.

Soundness

We need to prove for any $y \not \in I \in \mathcal {P}(2t+1)$

$$ \sum\limits_{x \in I \,\,\textit{and}\,\, x < y} \text{ord}_{2}(y - x) = \sum\limits_{x \in I \,\,\textit{and}\,\, x < y} \text{ord}_{2}(y+x+2t+2). $$

(14)

Let us prove by case analysis according to the patterns of y and I.

Case 1

y ∈ (0, 0, α) and I = (1, ?, β), where $(0, \alpha ), (1, \beta ) \in \mathcal {P}(t)$. Both the left and right of (14) are 0.

Case 2

y ∈ (0, 0, α) and I = (0,1,β), where $(0, \alpha ), (1, \beta ) \in \mathcal {P}(t)$. The left of (14) is |I ∩ [0, y − 1]|, and the right is ${\sum }_{x \in I \cap [0, y-1]} \text {ord}_{2}(y+x+2t+2) = \sum \text {ord}((0, 0, y_{\ge 2}) + (0, 1, x_{\ge 2}) + (0, t+1)) = |I \cap [0,y-1]|$.

Case 3

y ∈ (1, ?, α) and I = (0, 0, β), where $(1, \alpha ), (0, \beta ) \in \mathcal {P}(t)$. Both the left and right of (14) are 0.

Case 4

y ∈ (1, ?, α) and I = (0,1,β), where $(1, \alpha ), (1, \beta ) \in \mathcal {P}(t)$. Both the left and right of (14) are 0.

Case 5

y ∈ (0, 1, α) and I = (0, 0, β), where $(1, \alpha ), (0, \beta ) \in \mathcal {P}(t)$. It is similar to Case 2.

Case 6

y ∈ (0, 1, α) and I = (1, ?, β), where $(1, \alpha ), (1, \beta ) \in \mathcal {P}(t)$. Both the left and right of (14) are 0.

Case 7

y ∈ (0, 0, α) and I = (0, 0, β), where $(0, \alpha ), (0, \beta ) \in \mathcal {P}(t)$ and α≠β. The left of (14) is

$$\begin{array}{@{}rcl@{}} && \sum\limits_{x_{\ge 1} \in (0, \alpha) \cap [0, y_{\ge 1}-1]} \text{ord}_{2}((0, y_{\ge 1}) - (0, x_{\ge 1})) \\ & = & |(0, \alpha) \cap [0, y_{\ge 1} - 1]| + \sum\limits_{x_{\ge 1} \in (0, \alpha) \cap [0, y_{\ge 1}-1]} \text{ord}_{2}(y_{\ge 1} - x_{\ge 1}), \end{array} $$

and the right of (14) is

$$\begin{array}{@{}rcl@{}} && \sum\limits_{x_{\ge 1} \in (0, \alpha) \cap [0, y_{\ge 1}-1]} \text{ord}_{2}((0, y_{\ge 1}) + (0, x_{\ge 1}) + (0, t+1)) \\ & = & |(0, \alpha) \cap [0, y_{\ge 1} - 1]| + \sum\limits_{x_{\ge 1} \in (0, \alpha) \cap [0, y_{\ge 1}-1]} \text{ord}_{2}(y_{\ge 1} + x_{\ge 1} + t+1). \end{array} $$

By induction hypothesis that $\mathcal {P}(t)$ is sound and $(0, \alpha ) \in \mathcal {P}(t)$, we have $\sum \text {ord}_{2}(y_{\ge 1} - x_{\ge 1}) = \sum \text {ord}_{2}(y_{\ge 1} + x_{\ge 1} + t+1)$, which implies (14).

Case 8

y ∈ (1, ?, α) and I = (1, ?, β), where $(1, \alpha ), (1, \beta ) \in \mathcal {P}(t)$ and α ≠ β. It is not difficult to verify that the left of (14) is

$$2|\alpha \cap [0, y_{\ge 2}-1]| + \sum\limits_{x_{\ge 2} \in \alpha \cap [0, y_{\ge 2}-1]} \text{ord}_{2}((1, y_{\ge 2}) - (1, x_{\ge 2})), $$

and the right of (14) is

$$2|\alpha \cap [0, y_{\ge 2}-1]| + \sum\limits_{x_{\ge 2} \in \alpha \cap [0, y_{\ge 2}-1]} \text{ord}_{2}((1, y_{\ge 2}) + (1, x_{\ge 2}) + t + 1). $$

By the induction hypothesis that $\mathcal {P}(t)$ is sound, and $(1, y_{\ge 2}) \in (1, \alpha ) \in \mathcal {P}(t)$, we have $\sum \text {ord}_{2}((1, y_{\ge 2}) - (1, x_{\ge 2})) = \sum \text {ord}_{2}((1, y_{\ge 2}) + (1, x_{\ge 2}) + t + 1),$ which implies (14).

Case 9

y ∈ (0, 1, α) and I = (0, 1, β), where $(1, \alpha ), (1, \beta ) \in \mathcal {P}(t)$ and α ≠ β. The left of (14) is

$$| \beta \cap [0, y_{\ge 2}] | + \sum\limits_{x_{\ge 2} \in \beta \cap [0, y_{\ge 2}-1]}\text{ord}_{2}((1, y_{\ge 2}) - (1, x_{\ge 2})) $$

and the right of (14) is

$$|\beta \cap [0, y_{\ge 2}]| + \sum\limits_{x_{\ge 2} \in \beta \cap [0, y_{\ge 2}-1]}\text{ord}_{2}((1, y_{\ge 2}) + (1, x_{\ge 2}) + t + 1). $$

By the induction hypothesis, $\mathcal {P}(t)$ is sound, then for $(1, y_{\ge 2}) \in (1, \alpha ) \in \mathcal {P}(t)$, $(1, \beta ) \in \mathcal {P}(t)$, we have $\sum \text {ord}_{2}((1, y_{\ge 2}) - (1, x_{\ge 2})) = \sum \text {ord}_{2}((1, y_{\ge 2}) + (1, x_{\ge 2}) + t + 1),$which proves (14).

Completeness

We will prove the completeness of $\mathcal {P}(2t + 1)$, which amounts to, for any $y \in I \in \mathcal {P}(2t+1)$ with {x ∈ I : x< y} nonempty,

$$ \sum\limits_{x \in I \,\,\text{and}\,\, x < y} \text{ord}_{2}(y - x) < \sum\limits_{x \in I \,\,\text{and}\,\, x < y} \text{ord}_{2}(y+x+2t+2). $$

(15)

Case 1

y ∈ I = (0, 0, α), where $y_{\ge 1} \in (0, \alpha ) \in \mathcal {P}(t)$. The left of (15) is

$$| I \cap [0, y-1]| + \sum\limits_{x_{\ge 1} \in (0, \alpha) \cap [0, y_{\ge 1}-1]} \text{ord}_{2}(y_{\ge 1} - x_{\ge 1}), $$

and the right of (15) is

$$| I \cap [0, y-1]| + \sum\limits_{x_{\ge 1} \in (0, \alpha) \cap [0, y_{\ge 1}-1]} \text{ord}_{2}(y_{\ge 1} + x_{\ge 1} + t + 1). $$

Observe that $y_{\ge 1} \in (0, \alpha ) \in \mathcal {P}(t)$ and (0, α)∩[0, y _≥1 − 1] is nonempty. By the completeness of $\mathcal {P}(t)$, we have $\sum \text {ord}_{2}(y_{\ge 1} - x_{\ge 1}) < \sum \text {ord}_{2}(y_{\ge 1} + x_{\ge 1} + t + 1)$, which implies (15).

Case 2

y ∈ I = (1, ?, α), where $(1, y_{\ge 2}) \in (1, \alpha ) \in \mathcal {P}(t)$. It is not difficult to verify the left hand side of (15) is

$$2 |\alpha \cap [0, y_{\ge 2}-1]| + \delta_{y_{1}, 1} + \sum\limits_{x_{\ge 2} \in \alpha \cap [0, y_{\ge 2}-1]} \text{ord}_{2}((1, y_{\ge 2}) - (1, x_{\ge 2})), $$

while the right of (15) is at least

$$2 |\alpha \cap [0, y_{\ge 2}-1]| + 2\delta_{y_{1}, 1} + \sum\limits_{x_{\ge 2} \in \alpha \cap [0, y_{\ge 2}-1]} \text{ord}_{2}((1, y_{\ge 2}) + (1, x_{\ge 2}) + t + 1). $$

Given (1, ?, α)∩[0, y − 1] nonempty, we either have (1,α)∩[0, y _≥2 − 1] nonempty, or y ₁ = 1. In the former case, ${\sum }_{x_{\ge 2}} \text {ord}_{2}((1, y_{\ge 2}) - (1, x_{\ge 2})) < {\sum }_{x_{\ge 2}} \text {ord}_{2}((1, y_{\ge 2}) + (1, x_{\ge 2}) + t + 1)$ by the completeness of $\mathcal {P}(t)$, which implies (15); in the latter case, (15) is also true.

Case 3

y ∈ I = (0, 1, α), where $(1, y_{\ge 2}) \in (1, \alpha ) \in \mathcal {P}(t)$. The left of (15) is

$$|(1, \alpha) \cap [0, y_{\ge 1}-1]| + \sum\limits_{x_{\ge 1} \in (1, \alpha) \cap [0, y_{\ge 1}-1]} (y_{\ge 1} - x_{\ge 1}), $$

while the right of (15) is

$$|(1, \alpha) \cap [0, y_{\ge 1}-1]| + \sum\limits_{x_{\ge 1} \in (1, \alpha) \cap [0, y_{\ge 1}-1]} (y_{\ge 1} + x_{\ge 1} + t + 1). $$

From the completeness of $\mathcal {P}(t)$, we have $\sum (y_{\ge 1} - x_{\ge 1})< \sum (y_{\ge 1} + x_{\ge 1} + t + 1)$, which implies (15).

4.5 $\mathcal {P}(\mathbb {F}_{2}, 2^{e} t+1)$, t odd, e ≥ 2

Recall the definition, for e ≥ 2 and odd t,

$$\mathcal{P}(2^{e}t+1) = \{ (1^{e}, \alpha) : \alpha \in \mathcal{P}(t+1)\} \cup \{ (1^{i}, 0, ?^{e-1-i}, \alpha) : \alpha \in \mathcal{P}(t), 0 \le i \le e-1 \}. $$

Soundness

We need to show for any $y \not \in I \in \mathcal {P}(2^{e} t+1)$

$$ \sum\limits_{x \in I \,\,\text{and}\,\, x < y} \text{ord}_{2}(y - x) = \sum\limits_{x \in I \,\,\text{and}\,\, x < y} \text{ord}_{2}(y+x+2^{e} t+2). $$

(16)

Again, it will be case analysis according to the definition.

Case 1

y ∈ (1^e, α) and I = (1ⁱ, 0, ?^{e − 1 − i}, β), where $\alpha \in \mathcal {P}(t+1)$ and $\beta \in \mathcal {P}(t)$. The left of (16) is i|β ∩ [0, y _{≥ e} − 1]|, and the right of (16) is

$$\sum\limits_{x_{\ge e} \in \beta \cap [0, y_{\ge e}-1]} \text{ord}_{2}((1^{e}, y_{\ge e}) + (1^{i}, 0, ?^{e-1-i}, x_{\ge e}) + (0, 1, 0^{e-2}, t)), $$

which is also i|β ∩ [0, y _{≥ e} − 1]|. Thus, (16) is true.

Case 2

y ∈ (1ⁱ, 0, ?^{e − 1 − i}, α) and I = (1^e, α). Similar with Case 1, both sides of (16) is i|β ∩ [0, y _{≥ e} − 1]|.

Case 3

y ∈ (1^e, α) and I = (1^e, β), where $\alpha , \beta \in \mathcal {P}(t+1)$ and α ≠ β. The left of (16) is $e |\alpha \cap [0, y_{\ge e}-1]| + {\sum }_{x_{\ge e} \in \beta \cap [0, y_{\ge e}-1]} \text {ord}_{2}(y_{\ge e} - x_{\ge e})$, while the right of (16) is

$$\begin{array}{@{}rcl@{}} & & \sum\limits_{x \in I \,\,\text{and}\,\, x < y} \text{ord}_{2}(y+x+2^{e} t+2) \\ && = \sum\limits_{x \in I \,\,\text{and}\,\, x < y} \text{ord}_{2}((1^{e}, y_{\ge e}) + (1^{e}, x_{\ge e}) + (0, 1, 0^{e-2}, t))\\ & & = e |\alpha \cap [0, y_{\ge e}-1]| + \sum\limits_{x_{\ge e} \in \beta \cap [0, y_{\ge e}-1]} \text{ord}_{2} (y_{\ge e} + x_{\ge e} + t + 2). \end{array} $$

By induction hypothesis, $\mathcal {P}(t+1)$ is sound. Combining with the facts that $\alpha \not = \beta \in \mathcal {P}(t+1)$ and y _{≥ e} ∈α, we have ${\sum }_{x_{\ge e}} \text {ord}_{2}(y_{\ge e} - x_{\ge e}) = {\sum }_{x_{\ge e}} \text {ord}_{2} (y_{\ge e} + x_{\ge e} + t + 2)$, which implies (16).

Case 4.1

y ∈ (1ⁱ, 0, ?^{e − 1 − i}, α) and I = (1^j, 0, ?^{e − 1 − j}, β), where $\alpha , \beta \in \mathcal {P}(t)$, and i ≠ j. The left of (16) is min(i, j)|I ∩ [0, y − 1]|, and the right of (16) is also min(i, j)|I ∩ [0, y − 1]|, because ord₂((1ⁱ,0, y _{i + 1},…,y _{e − 1}, y _{≥ e} )+(1^j, 0, ?^{e − 1 − j},∗)+(0^e, t)+(0,1))= min(i, j).

Case 4.2

y ∈ (1ⁱ, 0, ?^{e − 1 − i}, α) and I = (1ⁱ, 0, ?^{e − 1 − i}, β), where $\alpha \not = \beta \in \mathcal {P}(t)$. The left of (16) is⁸

$$\begin{array}{@{}rcl@{}} && \sum\limits_{x_{\ge e} \in \beta \cap [0, y_{\ge e}-1]} \text{ord}_{2}((1^{i}, 0, y_{i+1}, \dots, y_{e-1}, y_{\ge e}) - (1^{i}, 0, ?^{e-1-i}, x_{\ge 2})) \\ && = (i+1) |I \cap [0, y-1]| + |\beta \cap [0, k_{\ge e}-1]| \left(\sum\limits_{j = 0}^{e-i-2} j 2^{e-i-j-2} + e-i-1\right) \\ & &\qquad +\sum\limits_{x_{\ge e} \in \beta \cap [0, y_{\ge e}-1]} \text{ord}_{2}(y_{\ge e}- x_{\ge e}), \end{array} $$

where the term j2^{e − i − j−2} corresponds to the sum over (1ⁱ,0, y _{i + 1},…,y _{i + j + 1},1 − y _{i + j + 2},?^{e − 1 − i − j}, x _{≥ e} ); the right of (16) is

$$\begin{array}{@{}rcl@{}} & & \sum\limits_{x_{\ge e} \in \beta \cap [0, y_{\ge e}-1]} \text{ord}_{2}((1^{i}, 0, y_{i+1}, \dots, y_{e-1}, y_{\ge e}) + (1^{i}, 0, ?^{e-1-i}, x_{\ge e}) + \\ & & (0, 1, 0^{e-2}, t)) \\ && = (i+1) |I \cap [0, y-1]| + |\beta \cap [0, k_{\ge e}-1]| (\sum\limits_{j = 0}^{e-i-2} j 2^{e-i-j-2} + e-i-1) \\ & & \qquad+\sum\limits_{x_{\ge e} \in \beta \cap [0, y_{\ge e}-1]} \text{ord}_{2}(y_{\ge e} + x_{\ge e} + t + 1). \end{array} $$

By the soundness of $\mathcal {P}(t)$, and the assumption that $y_{\ge e} \in \alpha , \beta \in \mathcal {P}$ and α ≠ β, we have ${\sum }_{x_{\ge e} \in \beta \cap [0, y_{\ge e}-1]} \text {ord}_{2}(y_{\ge e}- x_{\ge e}) = {\sum }_{x_{\ge e} \in \beta \cap [0, y_{\ge e}-1]} \text {ord}_{2}(y_{\ge e} + x_{\ge e} + t + 1)$, which proves (16).

Completeness

It suffices to prove, for any $y \in I \in \mathcal {P}(2t+1)$ with {x ∈ I : x< y} nonempty,

$$ \sum\limits_{x \in I \,\,\text{and}\,\, x < y} \text{ord}_{2}(y - x) < \sum\limits_{x \in I \,\,\text{and}\,\, x < y} \text{ord}_{2}(y+x+2^{e} t+2). $$

(17)

Case 1

y ∈ I = (1^e, α), where $\alpha \in \mathcal {P}(t+1)$. In this case, the left of (17) is $e |I \cap [0, y-1]| + {\sum }_{x_{\ge e} \in \alpha } (y_{\ge e} - x_{\ge e}),$ and the right of (17) is

$$\begin{array}{@{}rcl@{}} && \sum\limits_{x_{\ge e} \in \alpha \cap [0, y_{\ge e}-1]} \text{ord}_{2}((1^{e}, y_{\ge e})+ (1^{e}, x_{\ge e}) + (0, 1, 0^{e-2}, t)) \\ & &= e |I \cap [0, y-1]| + \sum\limits_{x_{\ge e} \in \alpha \cap [0, y_{\ge e}-1]} \text{ord}_{2}(y_{\ge e} + x_{\ge e} + t + 2). \end{array} $$

By the completeness of $\mathcal {P}(t+1)$, and the condition $y_{\ge e} \in \alpha \in \mathcal {P}(t+1)$, we have ${\sum }_{x_{\ge e}} (y_{\ge e} - x_{\ge e}) < {\sum }_{x_{\ge e}} \text {ord}_{2}(y_{\ge e} + x_{\ge e} + t + 2)$, which proves (17).

Case 2

$y \in I = (1^{i}, 0, ?^{e-1-i}, \alpha ) \in \mathcal {P}(2^{e}t+1)$, where $\alpha \in \mathcal {P}(t)$. The left of (17) is

$$\begin{array}{@{}rcl@{}} && \sum\limits_{x_{i+1}, \ldots, x_{e-1} \in \{0, 1\}, x_{\ge e} \in \alpha \atop : (1^{i}, 0, x_{\ge i+1}) < y} \text{ord}_{2}((1^{i}, 0, y_{\ge i+1}) - (1^{i}, 0, x_{i+1}, \ldots, x_{e-1}, x_{\ge e})) \\ && = (i+1) |I \cap [0, y-1]| + \sum\limits_{x_{\ge e} \in \alpha} \text{ord}_{2}((y_{i+1}, \ldots, y_{e-1}, y_{\ge e}) - (?^{e-i-1}, x_{\ge e})) \\ & &\quad+ \sum\limits_{x_{i+1}, \ldots, x_{e-1} \in \{0, 1\} \atop : (x_{i+1}, \ldots, x_{e-1}) < (y_{i+1}, \ldots, y_{e-1})} \text{ord}_{2}((y_{i+1}, \ldots, y_{e-1}, y_{\ge e})- (x_{i+1}, \ldots, x_{e-1}, y_{\ge e})). \end{array} $$

The right of (17) is

$$\begin{array}{@{}rcl@{}} & & \sum\limits_{x_{i+1}, \ldots, x_{e-1} \in \{0, 1\}, x_{\ge e} \in \alpha \atop : (1^{i}, 0, x_{\ge i+1}) < y} \text{ord}_{2}((1^{i}, 0, y_{\ge i+1}) + (1^{i}, 0, x_{\ge i+1}) + (0, 1, 0^{e-2}, t)) \\ & &= (i+1) |I \cap [0, y-1]| + \sum\limits_{x_{\ge e} \in \alpha} \text{ord}_{2}(y_{\ge i+1} + (?^{e-i-1}, x_{\ge e}) + (1, 0^{e-i-2}, t)) \\ & & \quad+\sum\limits_{x_{i+1}, \ldots, x_{e-1} \in \{0, 1\} \atop : (x_{i+1}, \ldots, x_{e-1}) < (y_{i+1}, \ldots, y_{e-1})} \text{ord}_{2}(y_{\ge i+1} + (x_{i+1}, \ldots, x_{e-1}, y_{\ge e}) + (1, 0^{e-i-2}, t)). \end{array} $$

Comparing the left with the right, if we could prove

$$\begin{array}{@{}rcl@{}} & & \sum\limits_{x_{\ge e} \in \alpha} \text{ord}_{2}((y_{i+1}, \ldots, y_{e-1}, y_{\ge e}) - (?^{e-i-1}, x_{\ge e})) \\ && \le \sum\limits_{x_{\ge e} \in \alpha} \text{ord}_{2}(y_{\ge i+1} + (?^{e-i-1}, x_{\ge e}) + (1, 0^{e-i-2}, t)) \end{array} $$

(18)

and

$$\begin{array}{@{}rcl@{}} & & \sum\limits_{x_{i+1}, \ldots, x_{e-1} \in \{0, 1\} \atop : (x_{i+1}, \ldots, x_{e-1}) < (y_{i+1}, \ldots, y_{e-1})} \text{ord}_{2}((y_{i+1}, \ldots, y_{e-1}, y_{\ge e})- (x_{i+1}, \ldots, x_{e-1}, y_{\ge e})) \\ && \le \sum\limits_{x_{i+1}, \ldots, x_{e-1}} \text{ord}_{2}(y_{\ge i+1} + (x_{i+1}, \ldots, x_{e-1}, y_{\ge e}) + (1, 0^{e-i-2}, t)) , \end{array} $$

(19)

and “ =” in (18), (19) can not hold simultaneously, then (17) will be true.

For (18), the left hand side is

$$|\alpha \cap [0, k_{\ge e}-1]| (\sum\limits_{j = 0}^{e-i-2} j2^{e-i-j-2} + e-i-1) + \sum\limits_{x_{\ge e} \in \alpha \cap [0, y_{\ge e}-1]}\text{ord}_{2}(y_{\ge e} - x_{\ge e}), $$

while the right is

$$|\alpha \cap [0, k_{\ge e}-1]| (\sum\limits_{j = 0}^{e-i-2} j2^{e-i-j-2} + e-i-1) + \sum\limits_{x_{\ge e} \in \alpha \cap [0, y_{\ge e}-1]}\text{ord}_{2}(y_{\ge e} + t + 1). $$

By the induction hypothesis that $\mathcal {P}(t)$ is complete, we have

$$\sum\limits_{x_{\ge e} \in \alpha \cap [0, y_{\ge e}-1]}\text{ord}_{2}(y_{\ge e} - x_{\ge e}) \le \sum\limits_{x_{\ge e} \in \alpha \cap [0, y_{\ge e}-1]}\text{ord}_{2}(y_{\ge e} + t + 1), $$

where the ≤ is strictly less if α ∩ [0, k _{≥ e} − 1] is nonempty.

For (19), the left is ${\sum }_{x = 0}^{y^{\prime }-1} \text {ord}_{2}(y^{\prime }-x) = \text {ord}_{2}(y^{\prime }!)$, where y′=(y _{i + 1},…,y _{e − 1}), and the right is at least ${\sum }_{x = 0}^{y^{\prime }-1} \text {ord}_{2}(y^{\prime }+x+1) = \text {ord}_{2}((2y^{\prime })!/y^{\prime }!)$. From (11), we know ord₂(y′)≤ord₂((2y′)!/y′!) unless y′=0. Suppose for contradiction that the “ =” holds in both (18) and (19) are true. Then y′=(y _{i + 1},…,y _{e − 1})=0 and α ∩ [0, y _{≥ e} − 1] is empty, which implies I ∩ [0, y − 1] is empty, which contradicts our assumption!

5 Proof for the case $\text {char}(\mathbb {F}) \ge 3$

For the case p ≥ 3, the idea of proving Lemma 4 is similar to that of p = 2. And the construction of $\mathcal {P}(\mathbb {F}_{p}, t)$ is in some sense simpler, where fewer cases are involved.

Within the section, p is always a prime greater than 2, and let q = (p + 1)/2. For convenience, we may write $\mathcal {P}(t)$ instead of $\mathcal {P}(\mathbb {F}_{p}, t)$, and we adopt the same p-adic expansion notation used in the last section.

Definition 4

Let p ≥ 3 be a prime, and q = (p + 1)/2. Define

$$\mathcal{P}(0) = \{ (\{x_{0}, p-1-x_{0}\}, \{x_{1}, p-1-x_{1}\}, {\ldots} )_{p} : 0 \le x_{i} \le q-1 \} $$

and

$$\mathcal{P}(1) = \{ ((p-1)^{i}, \{j, p-2-j\}, \alpha)_{p} : \alpha \in \mathcal{P}(0), i \ge 0, j = 0, 1, \ldots, q-2 \}, $$

where {j, p−2 − j} denotes a bit which is either j or p−2 − j. For any integer t ≥ 0 and 0 ≤ r ≤ p − 1 with p t + r ≥ 2, define

$$\begin{array}{@{}rcl@{}} & & \mathcal{P}(pt + r) \\ && = \{ (\{i, j\}, \alpha)_{p} : 0 \le i, j \le p-1, b \in \{1,2\}, i+j+r+1=bp, \alpha \in \mathcal{P}(t+b-1) \}. \end{array} $$

To help understand the definition, let us redefine the partition in standard set notations instead of “patterns”. Partition $\mathcal {P}(0) = \{I_{0}, I_{1}, {\ldots } \}$, where

$$\begin{array}{@{}rcl@{}} I_{j} & = & \{ x = (x_{0}, x_{1}, \ldots)_{p} : \sum\limits_{i : x_{i} \le q-1} x_{i} q^{i} + \sum\limits_{i : x_{i} \ge q} (p-1-x_{i}) q^{i} = j \}. \\ \mathcal{P}(1) & = & \{ (p^{i+1} I + j p^{i} + p^{i}-1) \cup (p^{i+1} I + (p-2-j) p^{i} + p^{i}-1) : \\ & & I \in \mathcal{P}(0), i \ge 0, j = 0, 1, \ldots, q-2\}. \\ \mathcal{P}(pt+r) & = & \{ (i + pI) \cup (j + pI) : 0 \le i, j \le p-1, b \in \{1, 2\}, i + j + r + 1 = bp, \\ & & I \in \mathcal{P}(t+b-1) \}. \end{array} $$

5.1 $\mathcal {P}(\mathbb {F}_{p}, 0)$

By the definition of $\mathcal {P}(0)$, every set in $\mathcal {P}(0)$ is uniquely identified by some pattern ({x ₀, p − 1 − x ₀},{x ₁, p − 1 − x ₁},…) _p , where x ₀, x ₁,…∈{0, 1,…, q − 1}.

Soundness

It suffices to prove, for any y∉I = ({z ₀, p − 1 − z ₀},{z ₁, p − 1 − z ₁},…) _p ,

$$ \sum\limits_{x \in I \cap [0, y-1]} \text{ord}_{p}(y-x) = \sum\limits_{x \in I \cap [0, y-1]} \text{ord}_{p}(y+x+1). $$

(20)

Let i be the minimum index such that y _i ∉{z _i , p − 1 − z _i }. (By assumption that y∉I, such i exists.) It is not difficult to see both the left and the right of (20) is

$$| (\{z_{i}, p-1-z_{i}\}, \{z_{i+1}, p-1-z_{i+1}\}, \ldots)_{p} \cap [0, y_{\ge i}-1] | \left(\sum\limits_{j = 1}^{i-1} j 2^{i-j-1} + i\right). $$

Completeness

It suffices to prove, for any y ∈ I with I ∩ [0, y − 1] nonempty,

$$ \sum\limits_{x \in I \cap [0, y-1]} \text{ord}_{p}(y - x) < \sum\limits_{x \in I \cap [0, y-1]} \text{ord}_{p}(y + x + 1). $$

(21)

Let I = ({z ₀, p − 1 − z ₀},{z ₁, p − 1 − z ₁},…) _p . Let i be an integer such that z _i = (p − 1)/2. The ith bit on the left of (21) is zero if x _j = y _j for all j ≤ i, and x _{≥ j} < y _{≥ j} ; and the ith bit on the right is zero if x _j = p − 1 − y _j for all j ≤ i, and x< y, which includes the case x _{≥ j} < y _{≥ j} . By a double counting argument, without loss of generality, assume such i does not exists, that is, for all i, z _i ≠(p − 1)/2.

Let $\phi : \mathbb {Z}_{\ge 0} \to \mathbb {Z}_{\ge 0}$ be the map

$$\phi(x) = (x^{\prime}_{0}, x^{\prime}_{1}, \ldots)_{2}, $$

where x = (x ₀, x ₁,…) _p is the p-adic expansion of x, and $x_{i}^{\prime } = 1$ if and only if x _i = max(x _i , p − 1 − x _i ), otherwise 0. Then, under our assumption that x _i ≠(p − 1)/2 for all i, (21) becomes

$$\sum\limits_{x \in [0, \phi(y)-1]} \text{ord}_{2}(\phi(y) - x) < \sum\limits_{x \in [0, \phi(y)-1]} \text{ord}_{2}(\phi(y) + x + 1), $$

which is equivalent to ord₂(ϕ(y)!)<ord₂((2ϕ(y))!/ϕ(y)!), which is exactly (11).

5.2 $\mathcal {P}(\mathbb {F}_{p}, 1)$

Soundness

We shall prove for any y∉I = ((p − 1)ⁱ,{j, p−2 − j},α) _p , j< p−2 − j, where $y \in ((p-1)^{i^{\prime }}, \{j^{\prime }, p-2-j^{\prime }\}, \beta )_{p}$, and $\alpha , \beta \in \mathcal {P}(0)$,

$$ \sum\limits_{x \in I\cap[0,y-1]} \text{ord}_{p}(y-x) = \sum\limits_{x \in I \cap [0, y-1]} \text{ord}_{p}(y+x+2). $$

(22)

Case 1

i ≠ i′. Both the left and right of (22) are min(i, i′)|I ∩ [0, y − 1]|.

Case 2

i = i′ and j ≠ j′. Both the left and right of (22) are i|I ∩ [0, y − 1]|.

Case 3

i = i′, j = j′ and α ≠ β. The left of (22) is

$$(i+1) |\alpha \cap [0, y_{\ge i+1}]| + \sum\limits_{x_{\ge i+1} \in\alpha \cap [0, y_{\ge i+1}]} \text{ord}_{p}(y_{\ge i+1} - x_{\ge i+1}), $$

and the right of (22) is

$$(i+1) |\alpha \cap [0, y_{\ge i+1}]| + \sum\limits_{x_{\ge i+1} \in\alpha \cap [0, y_{\ge i+1}]} \text{ord}_{p}(y_{\ge i+1} + x_{\ge i+1} + 1). $$

Since $\mathcal {P}(0)$ is sound, and $y_{\ge i+1} \not \in \alpha \in \mathcal {P}(0)$, we have ${\sum }_{x_{\ge i+1}}\text {ord}_{p}(y_{\ge i+1} - x_{\ge i+1}) = {\sum }_{x_{\ge i+1}} \text {ord}_{p}(y_{\ge i+1} + x_{\ge i+1} + 1),$which implies (22).

Completeness

We need to prove for any $y \in I = ((p-1)^{i}, \{j, p-2-j\}, \alpha )_{p} \in \mathcal {P}(1)$ with I ∩ [0, y − 1] nonempty,

$$ \sum\limits_{x \in I \cap [0, y-1]} \text{ord}_{p}(y - x) < \sum\limits_{x \in I \cap [0, y-1]} \text{ord}_{p}(y+x+2). $$

(23)

The left side of (23) is

$$\begin{array}{@{}rcl@{}} && \sum\limits_{x_{i} \in \{j, p-2-j\}, x_{\ge i+1} \in \alpha : x < y} \text{ord}_{p}(((p-1)^{i}, y_{i}, y_{\ge i+1})_{p} - ((p-1)^{i}, x_{i}, x_{\ge i+1})_{p}) \\ & &= (2i+1) |\alpha \cap [0, y_{\ge i+1}-1]| + i \delta_{y_{i}, p-2-j} + \sum\limits_{x_{\ge i+1} \in \alpha \atop x_{\ge i+1} < y_{\ge i+1}} \text{ord}_{p}(y_{\ge i+1} - x_{\ge i+1}), \end{array} $$

and the right of (23) is

$$\begin{array}{@{}rcl@{}} & & \sum\limits_{x_{i} \in \{j, p-2-j\}, x_{\ge i+1} \in \alpha : x < y} \text{ord}_{p}(((p-1)^{i}, y_{i}, y_{\ge i+1})_{p} + ((p-1)^{i}, x_{i}, x_{\ge i+1})_{p} + 2) \\ & \ge & (2i+1) |\alpha \cap [0, y_{\ge i+1}-1]| + (i + 1) \delta_{y_{i}, p-2-j} + \sum\limits_{x_{\ge i+1} \in \alpha \atop x_{\ge i+1} < y_{\ge i+1}} \text{ord}_{p}(y_{\ge i+1} + x_{\ge i+1}+1). \end{array} $$

Since $\mathcal {P}(0)$ is complete, we have

$$\sum\limits_{x_{\ge i+1} \in \alpha} \text{ord}_{p}(y_{\ge i+1} - x_{\ge i+1}) < \sum\limits_{x_{\ge i+1} \in \alpha} \text{ord}_{p}(y_{\ge i+1} + x_{\ge i+1}+1) $$

if α ∩ [0, y _{≥ i + 1} − 1] is not empty, in which (23) is true. Otherwise, by assumption I ∩ [0, y − 1] is nonempty, we have y _i = p−2 − j, which also implies (23).

5.3 $\mathcal {P}(\mathbb {F}_{p}, pt+r)$

By definition, $\mathcal {P}(pt + r) = \{ (\{i, j\}, \alpha )_{p} : 0 \le i, j \le p-1, b \in \{1, 2\}, i+j+r+1 = bp, \alpha \in \mathcal {P}(t + b-1) \}.$

Soundness

We will prove for any $y \not \in I = (\{i^{\prime }, j^{\prime }\}, \beta )_{p} \in \mathcal {P}(pt+r)$, where y ∈ ({i, j},α) _p ,

$$ \sum\limits_{x \in I \cap [0, y-1]} \text{ord}_{p}(y - x) = \sum\limits_{x \in I \cap [0, y-1]} \text{ord}_{p}(y+x+pt+r+1). $$

(24)

Without loss of generality, assume i = i′ and j = j′, otherwise both sides of (24) are 0. By definition, i + j + r + 1=b p, where b ∈ {1,2}, and $\alpha \not = \beta \in \mathcal {P}(t+b-1)$. The left hand side of (24) is

$$|I \cap [0, y -1]| + \sum\limits_{x_{\ge 1} \in \beta \cap [0, y_{\ge 1}-1]} \text{ord}_{p}(y_{\ge 1} - x_{\ge 1}), $$

and the right of (24) is

$$\begin{array}{@{}rcl@{}} & & \sum\limits_{x_{\ge 1} \in \beta \cap [0, y_{\ge 1}-1]} \text{ord}_{p}((y_{0}, y_{\ge 1})_{p} + (\{i, j\}, x_{\ge 1})_{p} + (r+1, t)_{p}) \\ && = |I \cap [0, y -1]| + \sum\limits_{x_{\ge 1} \in \beta \cap [0, y_{\ge 1}-1]} \text{ord}_{p}(y_{\ge 1} + x_{\ge 1} + t + b). \end{array} $$

By induction hypothesis, $\mathcal {P}(t+b-1)$ is sound, we have ${\sum }_{x_{\ge 1}} \text {ord}_{p}(y_{\ge 1} - x_{\ge 1}) = {\sum }_{x_{\ge 1}} \text {ord}_{p}(y_{\ge 1} + x_{\ge 1} + t + b)$, which proves (24).

Completeness

We prove, for any $y \in I = (\{i, j\}, \alpha ) \in \mathcal {P}(pt+r)$ with I ∩ [0, y − 1] nonempty, and i< j,

$$ \sum\limits_{x \in I \cap [0, y-1]} \text{ord}_{p}(y - x) < \sum\limits_{x \in I \cap [0,y-1]} \text{ord}_{p}(y+x+pt+r+1), $$

(25)

where i + j + r + 1=b p, b ∈ {1,2}, and $\alpha \in \mathcal {P}(t+b-1)$. The left of (25) is

$$|\alpha \cap [0, y_{\ge 1}-1]| + \sum\limits_{x_{\ge 1} \in \alpha \cap [0, y_{\ge 1}-1]}\text{ord}_{p}(y_{\ge 1} - x_{\ge 1}), $$

and the right of (25) is

$$\begin{array}{@{}rcl@{}} & & \sum\limits_{x_{\ge 1} \in \alpha \cap [0, y_{\ge 1}-1]} \text{ord}_{p}((y_{0}, y_{\ge 1})_{p} + (\{i, j\}, x_{\ge 1})_{p} + (r+1, t)_{p}) \\ &&\ge |\alpha \cap [0, y_{\ge 1}-1]| + \delta_{y_{0}, j} + \sum\limits_{x_{\ge 1} \in \alpha \cap [0, y_{\ge 1}-1]} \text{ord}_{p}(y_{\ge 1} + x_{\ge 1} + t + b). \end{array} $$

By the induction hypothesis that $\mathcal {P}(t+b-1)$ is complete, then

$$\sum\limits_{x_{\ge 1} \in \alpha \cap [0, y_{\ge 1}-1]}\text{ord}_{p}(y_{\ge 1} - x_{\ge 1}) < \sum\limits_{x_{\ge 1} \in \alpha \cap [0, y_{\ge 1}-1]} \text{ord}_{p}(y_{\ge 1} + x_{\ge 1} + t + b) $$

if α ∩ [0, y _≥1 − 1] is nonempty, in which case (25) is true; otherwise, y ₀ = j > i, which also implies (25). The author would like to thank Alexander Razborov for helpful discussions which make the author consider general t in Theorem 1, and thank anonymous reviewers for their comments and suggestions which improve the presentation.