Multivariate Binary Representation

Published on May 22, 2024

In this blog post, I introduce Multivariate Binary Representation: A method for encoding the binary expansions of integers as multivariate monomials using a polynomial quotient ring. This encoding process involves modular exponentiation within a specific ring structure, referred to as $S_b$ , to uniquely represent any positive integer $n$ .

Let $b = \left\lfloor \log_2 n \right\rfloor + 1$ . Consider the recursive polynomial quotient ring [1]

$\begin{align*} S_b = \mathbb{Z}[x_0, x_1, \ldots, x_b]/I_b , \end{align*}$

where the ideal

$\begin{align*} I_b = \langle x_0^2 - x_1, x_1^2 - x_2, \ldots, x_{b-1}^2 - x_{b}, x_b^2 \rangle . \end{align*}$

In $S_b$ , we adopt the dlex monomial ordering $x_0 > x_1 > \cdots > x_b$ . Within the ring $S_b$ , the variables $x_i$ satisfy the recursive relation $x_i^2 = x_{i+1}$ for $1 \leq i < b$ , where $x_{i+1}$ refers to the next variable in the sequence, and $x_b^2 = 0$ .

Encoding

Expanding $x_0^n$ in $S_b$ gives a unique combinatorial representation of $n$ as a monomial in variables $x_0,\ldots, x_{b-1}$ . Consider $x_0 \in S_b$ . The expansions for $n=1,\ldots,16$ are given below:

$\begin{align*} x_0^1 &= x_0 \\ x_0^2 &= x_1 \\ x_0^3 &= x_0 x_1 \\ x_0^4 &= x_2 \\ x_0^5 &= x_0 x_2 \\ x_0^6 &= x_1 x_2 \\ x_0^7 &= x_0 x_1 x_2 \\ x_0^8 &= x_3 \\ x_0^9 &= x_0 x_3 \\ x_0^{10} &= x_1 x_3 \\ x_0^{11} &= x_0 x_1 x_3 \\ x_0^{12} &= x_2 x_3 \\ x_0^{13} &= x_0 x_2 x_3 \\ x_0^{14} &= x_1 x_2 x_3 \\ x_0^{15} &= x_0 x_1 x_2 x_3 \\ x_0^{16} &= x_4 \\ \vdots & \end{align*}$

To clarify, on the righthand side we have taken $x_0^n$ modulo the ideal $I_b$ .

Notice that the $x_i$ within the expansion of $x_0^n \pmod {I_b}$ correspond to the positions of $1$ bits in the binary expansion of $n$ .

Example: Encoding.
Consider $n=11$ . Here, we have $b = \left\lfloor \log_2 11 \right\rfloor + 1 = 4$ . Expanding $x^{11}$ in our ring $S_4$ gives

$\begin{align*} x^{11} \equiv x_0 x_1 x_3 \pmod{I_4} . \end{align*}$

We compare the above result to the binary expansion of $11$ , which is

$\begin{align*} s_2(11) = 2^0 + 2^1 + 2^3 . \end{align*}$

Decoding

To convert $x_0^n \pmod{I_b}$ back to binary, the simplest method is to enumerate the indices of the variables in the monomial and sum the corresponding powers of two.

Example: Decoding.
Let $n=11$ , hence $x^{11} \equiv x_0 x_1 x_3 \pmod{I_4}$ . To decode, we compute $x_i = f_{11} = x^{11} \bmod I_4 = x_0 x_1 x_3$ . Summing the corresponding powers of two for $x_0,x_1,x_3$ yields

$\begin{align*} 2^0 + 2^1 + 2^3 = 11 . \end{align*}$

Unusual Properties of $x_0$ in $S_b$

The element $x_0$ in the ring $S_b$ possesses unusual root extraction and discrete logarithm properties. In $S_b$ , each power $x_0^n$ corresponds uniquely to a multivariate monomial modulo the ideal $I_b$ . This mapping provides an analogy to the discrete logarithm

$\begin{align*} x_0^n \equiv x_{\alpha} \cdots x_{\omega} \pmod{I_b} , \end{align*}$

where $x_{\alpha} \cdots x_{\omega}$ is the unique combinatorial representation of the integer $n$ . Just as the discrete logarithm function uniquely determines the exponent in modular arithmetic, $x_0^n$ uniquely determines $n$ in $S_b$ .

Another potentially interesting property is that $x_0$ serves as the $k$ -th root of all integers $k$ within the range $1 \leq k \leq n$ . Specifically, $x_0$ is the $k$ -th root of the element representing $k$ in $S_b$ . For instance, $x_0$ is the $16$ th root of $x_4$ in $S_4$ :

$\begin{align*} x_0^{16} = x_4 \pmod{I_4} . \end{align*}$

The utility of these properties remains an open question for now.

Source Code

Below is Sage code which encodes and decodes a range of integers to multivariate binary, printing the results in CSV format.

# Joseph Shunia, (C) 2024
n_min, n_max = 1, 16
b_max = floor(log(n_max,2))+1
R = PolynomialRing(ZZ, b_max+1, 'x')
x = R.gens()
I_list = [x[i]^2 - x[i+1] if i < b_max else x[i]^2 for i in range(b_max + 1)]
subs_dict = {x[i]: 2^i for i in range(b_max + 1)}
I = R.ideal(I_list)
G = I.groebner_basis()
S = R.quotient(I, 'x')

def mvb_encode(n):
    return S(x[0]^n)
    
def mvb_decode(poly):
    sum = 0
    vars = poly.monomials()[0].variables()
    for v in vars:
        sum += subs_dict[v]
    return sum
    
print(f'n, encoded, decoded')
for n in range(n_min, n_max+1):
    n_encoded = mvb_encode(n)
    n_decoded = mvb_decode(n_encoded)
    print(f'{n}, {n_encoded}, {n_decoded}')

If you want to run the code in your browser, you can use SageCell.

Related Works

Multivariate binary representation shares similarities to Boolean polynomials [2], which are defined over the ring $\mathbb{F}_2[x_0,\ldots, x_n]/J_n$ , where the ideal $J_n = \left\langle x_0^2 + x_0, \ldots, x_n^2 + x_n \right\rangle$ .

A fundamental difference is that an integer $n$ is encoded to multivariate binary representation by way of exponentiation, whereas the encoding process is performed manually for Boolean polynomials by examining the binary expansion of $n$ (similar to how our decoding process is performed). Also, in multivariate binary, the encoded representation is a single monomial, as opposed to a sum of monomials. Furthermore, in Boolean polynomials, all coefficients are taken modulo $2$ , which is not necessarily the case in the ring $S_b$ .

To illustrate these differences, here is the encoded representation of $n=11$ as a Boolean polynomial:

$\begin{align*} \mathrm{boolean\_poly\_encode}(11) = x_0 + x_1 + x_3 , \end{align*}$

where the function $\mathrm{boolean\_poly\_encode}(n)$ performs the encoding by examining the binary expansion of $n$ .

Joseph Shunia's Blog

Multivariate Binary Representation

Encoding

Decoding

Unusual Properties of $x_0$ in $S_b$

Source Code

Related Works

Further Reading

Leave a Reply Cancel reply

Multivariate Binary Representation

Encoding

Decoding

Unusual Properties of in

Source Code

Related Works

Further Reading

Leave a Reply Cancel reply

Unusual Properties of $x_0$ in $S_b$