Introduction

This document will go over why comparing integers in an arithmetic circuit is not simply $a < b$ .

TLDR

In order to compare two elements $a$ and $b$, there needs to be a notion of ordering. Finite fields/fields with prime characteristic are un-ordered. So we interpret elements as bit-width integers before comparing, which explicitly specifies a range that the bit representation of the field element must fall into.

What is the characteristic of a field?

Take an element $a$ from the additive group of a field $F_p$, the characteristic is the smallest n such that $$\underbrace{a + a + \cdots + a}_{n} = 0,$$

If the field has no n such that the above is true, we say that the characteristic of the field is $0$. An example of such a field is $ \mathbb{R}$.

The characteristic of a field is either 0 or it is prime.

Prime characteristic - Unordered

If a finite field has prime characteristic, then it is un-ordered.

If there is ordering, then we can say:

• All positive numbers are greater than zero.
• The sum of two positive numbers, will also be greater than zero

Semi proof

Lets assume that our field with characteristic n is ordered.

Now assume that $a$ is positive:

$$a > 0$$

Add $a$ ,$n-1$ times to both sides.

$a + \underbrace{a + a + \cdots + a}_{n-1} > \underbrace{a + a + \cdots + a}_{n-1}$

Since the field has a characteristic of n, this can be simplified to be:

$$0 > \underbrace{a + a + \cdots + a}_{n-1}$$

Since the sum of two positive numbers is also positive in an ordered field, then the rhs is also some positive element $b$.

$$ 0 > b $$

The last line is a contradiction. The same logic follows if we assume that our element is negative.

Zero characteristic - Ordered

Note above that the only reason we came to a contradiction was because we could add $n-1$ elements of $a$ to both sides, and it essentially “wrapped/returned” us back to $0$.

This property is not available with fields of characteristic zero.

For more details on the above, you could google “ordered fields”

How do we solve this in practice?

The problem stems from this “wrap around” property that the finite field possesses. In order to mitigate this, we only need to supply an upper bound, which is smaller than the finite fields order.

Example

$F_{11} = {[0]{11},[1]{11},[2]{11},[3]{11},[4]{11},[5]{11},[6]{11},[7]{11},[8]{11},[9]{11},[10]_{11}}$

where $[r]_{11}$ = ${ 11k+r : k,r\in \mathbb{Z}}$ is the residue/congruence/equivalence class

However in practice, we usually abuse notation and write our field using representative numbes:

$$F_{11} = {0,1,2,3,4,5,6,7,8,9,10}$$

Is 3 < 5 ?

• We specify the upperbound as $[0,2^{3})$ ie we interpret both 3 and 5 as u3 integers. Now we can compare them! 3 is less than 5 when we only look at the range $[0,2^{3})$

Is 14 < 5 ?

Since $F_{11}$ is unordered, we cannot compare these as field elements; you could say that 14 < 5 is false, but then another person could then say, since we are in $F_{11}$, this is the same as 3 < 5, so it’s true.

To solve this ambiguity, we interpret both elements as u3s. To which we note that 14 cannot be stored as a u3!

Why did I pick u3?

If I had chosen u32 we still would not be able to distinguish between 3 and 14, since they both lie in the range of a u32. In practice, the fields are large enough where elements can be interpreted as u32, u64 and even u128.