48 A non-symmetric example - Inequality

Write ${\mathrm{LEQ}}^n:\{0,1{\}}^n\times .\{0,1{\}}^n\to \{0,1\}$ b:

$${\mathrm{LEQ}}^n(\overrightarrow{x},\overrightarrow{y})=1⟺\text{ number coded by }\overrightarrow{x}\le \text{ number coded by }\overrightarrow{y}$$

Notice that ${\mathrm{LEQ}}^n$ satisfies the following recurrence:

$$\begin{array}{r}{\mathrm{LEQ}}^1(x,y)=\neg x\vee y\\ {\mathrm{LEQ}}^{n+1}(\overrightarrow{x}{x}_{n+1},\overrightarrow{y}{y}_{n+1})=\{\begin{array}{l}{\mathrm{LEQ}}^n(\overrightarrow{x},\overrightarrow{y})\wedge {\mathrm{NEQ}}^n(\overrightarrow{x},\overrightarrow{y})x_{n+1}\wedge \neg y_{n+1}\\ {\mathrm{LEQ}}^n(\overrightarrow{x},\overrightarrow{y})\text{otherwise}\end{array}\end{array}$$

where ${\mathrm{NEQ}}^n(\overrightarrow{x},\overrightarrow{y})=1$ just if $\overrightarrow{x}\ne \overrightarrow{y}$.

NB: ${\mathrm{NEQ}}^n(\overrightarrow{x},\overrightarrow{y})={\bigvee }_{i=1}^n(\neg x_1\wedge y_1)\vee (x_1\wedge \neg y_1)$ which are formulas of size $O(n)$ (so, in particular, linear-size circuits).