Modular exponential in recursive and weak arithmetic complexity classes
by
Henri-Alex Esbelin
llaic1

Some known algorithms are devoted to the problem of comparing big integers using only small integers, through modular arithmetic. This paper is devoted to the problem of comparing exponentially defined numbers using number of size less than the exponents. The main result is the following:

The binary relation on  \naturel   with x and y as variables defined by a^x < b^y is in the least class of the Grzegorczyck's hierarchy.

We will then discuss some easy natural generalizations of this result, and the following conjecture

Does the binary relation on N with x and y as variables defined by a^x < b^y lies in the least class of relations on N containing sum and product relations and quaternary modular exponentiation, and is closed under explicit transformations, boolean operations, variable bounded quantifications and counting schema?

Sketch of the proof of the main result.

Let us denote (p_i)_{0 <= i <= n} a finite sequence of prime integers. Suppose that X < \prod_i=0ⁱ⁼ⁿp_i and Y < \prod_i=0ⁱ⁼ⁿp_i. Let us denote \prod_i=kⁱ⁼ⁿp_i=P_k ad P_n+1=1.

Let us recursively define the following two sequences (X_k)_{0 <= i <= n} and (Y_k)_{0 <= i <= n} by X₀=X and X_k+1 = X_kmod(P_k+1), resp. by Y₀=Y and Y_k+1 = Y_kmod(P_k+1).

Then we have the following lemma:

X < Y if and only if some integer i exists such that for all integer j strictly less than i, we have \lfloorX_j/P_j+1\rfloor = \lfloorY_j/P_j+1\rfloor and \lfloorX_i/P_i+1\rfloor < \lfloorY_i/P_i+1\rfloor.

Let us denote ((a/b))mod(c) the unique integer d in {0, ..., c-1} such that a \equiv bdmod(c).

Then we prove the following lemma

Let us define the following sequence (depending of the (p_i)_{1 <= i <= n} sequence)

U(X, k, 1)=X mod(p_k) and

U(X, k, i+1)=U(X, k, i) + (prodj=kj=k+ipj) ×(((X mod(pk+i+1)-U(X, k, i))/prodj=kj=k+ipj)) mod(pk+i+1)

Then \lfloorX_k/P_k+1\rfloor = U(X, k+1, n-k-1) mod(p_k).

Date received: April 12, 2002