## Generating positive polynomials that are not sums of squares

Motivation: “To prove that P=NP”. More seriously, there is a very powerful technique, called Sum of Squares (SOS) of polynomials in the optimization. For instance, if $f(x) = \sum_i g_i^2(x), x \in \mathbb{R}^n$, where $f(x)$ and $g_i(x)$ are some polynomials it is obvious that $f(x)$ is non-negative. Unfortunately, this does not work in opposite direction. There are examples of positive polynomials that are not a sum of squares of other polynomials. Therefore, automatic generation of non-negative polynomials that are not sums of squares allows to extend applicability of SOS technique. If we would be enable to generate enough of such polynomials the global minimum of any polynomial function $f(x)$ would be accessible. Consequently, P would be equal NP. This post has modest goal is to understand how to generate algorithmically a single positive polynomial that is not a sum of squares of other polynomials in arbitrary dimension. In a sense this is a formalization of previous post.

Preliminaries

Let $x \in \mathbb{R}^n, \alpha \in \mathbb{ N }_{0}^n, \mathbb{X}^d = \{ X = \prod_k X_k^{\alpha_k} | \sum_k \alpha_k \leq d \}$, where $X_k$ is an arbitrary unique symbol denoting variable. For example, $\mathbb{X}^0= \{ 1 \}, \mathbb{X}^1= \{ 1, X_1, X_2, ..., X_n \}$. Let $\mathbb{X}^d(x)$ being evaluation of the set $\mathbb{X}^d$ at point $x$. For example, $\mathbb{X}^0(x)= \{ 1 \}$ for any point x, $\mathbb{X}^1( (0,1) )= \{ 1, 0, 1 \}$. $\mathbb{X}^2( (0,1) )= \{ 1, 0, 1, 0, 1, 0 \}$, where $\mathbb{X}^2 = \{ 1, X_1, X_2, ..., X_n, X_1^2, X_2^2, ... X_N^2, X_1 X_2, X_1 X_3, ... X_{n-1} X_n \}$. Let polynomial be a linear combination of elements of $\mathbb{X}^d : f(x) = \sum_k c_k \mathbb{X}^d_k$, where $\mathbb{X}^d_k$ enumerates elements of the set.

NP-complete integer partition problem

Let $a_i \in \mathbb{N}, \xi_i \in {\pm1}$. Integer partition problem is asking whether $\exists \xi : \sum_k a_k \xi_k =0$, e.g. whether it is possible to divide set of integers into two complementary sets that have equal sum. This problem is NP-complete.

Proposition 1 Integer partition problem is equivalent to the question whether global minimum of polynomial $\sum_k (X_k^2-1)^2 + \left( \sum_k a_k X_k \right)^2$ is greater than zero or not.

Proof Since the polynomial is a sum of squares of real variables, it is non-negative and can be zero only when each term is zero. the first sum can only be zero at the values of $x_k= \{\pm1\}$. The second sum at given values can be zero only when partition exists $\blacksquare$

Corollary To prove P=NP it is sufficient to analyse quartic polynomials.
Proof Obvious $\blacksquare$

Here we would like to establish some properties of the quadratic polynomials on the hyper-cube $\mathbb{H} = \{ x \in \{0; 1\}^n \}$

Propostiion 2 Consider quadratic polynomial $f(x)$. If $f(x) = 0, \forall x~\in~\tilde{ \mathbb{H} }, \tilde{ \mathbb{H} } = \{ x: x~\in~\mathbb{H}, \sum_k x_k \leq 2 \}$ than $f(x) =0, \forall x \in \mathbb{H}$.

Proof
$f(x)= c_1+ \sum_k c_{X_k} X_k + c_{X_k^2} X_k^2 + \sum \limits_{j \neq k} c_{X_j X_k} X_j X_k$
Consequitively,
$x=0 \Rightarrow c_1=0$.
$\sum_k x_k =1 \Rightarrow x_k=1, x_{j \neq k}=0 \Rightarrow c_{X_k} + c_{X_k^2}=0$.
$\sum_k x_k =2 \Rightarrow x_k =1, x_j=1, x_{ l \neq k,j }=0 \Rightarrow c_{X_kX_j}=0$, taking into account second case.

Finally, $f(x) = \sum_k c_{X_k} X_k(X_k-1)$, which is clearly 0 for $x \in \mathbb{H}$, since in each term in the sum either first or second factor is 0 $\blacksquare$

Quartics that vanish on $\tilde{ \mathbb{H} }$
$f(x)= c_1+ \sum_k c_{X_k} X_k + c_{X_k^2} X_k^2 + c_{X_k^3}X_k^3 +c_{X_k^4}X_k^4 +\sum \limits_{j \neq k} c_{X_j X_k} X_j X_k + c_{X_j^2 X_k} X_j^2 X_k+ c_{X_j^3 X_k} X_j^3 X_k+ c_{X_j^2 X_k^2} X_j^2 X_k^2+ \sum \limits_{j \neq k \neq m} c_{X_j X_k X_m} X_j X_k X_m + c_{X_j^2 X_k X_m} X_j^2 X_k X_m + \sum \limits_{j \neq k \neq m \neq l} c_{X_j X_k X_m X_l} X_j X_k X_m X_l$.

Consequently,
$x=0 \Rightarrow c_1=0$.
$\sum_k x_k =1 \Rightarrow x_k=1, x_{j \neq k}=0 \Rightarrow c_{X_k} + c_{X_k^2} + c_{X_k^3} + c_{X_k^4}=0$.
$\sum_k x_k =2 \Rightarrow x_k =1, x_j=1, x_{ l \neq k,j }=0 \Rightarrow c_{X_j X_k} + c_{X_j^2 X_k}+ c_{X_j^3 X_k}+ c_{X_j^2 X_k^2}=0$, taking into account second case.

Additionally, we want quartics to preserve sign around $x \in \tilde{ \mathbb{H} }$, since we are interested in positive polynomials. Necessary condition is that gradient equals 0 for corresponding points.

$\frac{ \partial f(x)}{ \partial X_q }= (c_{X_k} + 2 c_{X_k^2} X_k + 3 c_{X_k^3}X_k^2 + 4 c_{X_k^4}X_k^3) \delta_{k,q} +\sum \limits_{j \neq k} (c_{X_j X_k} X_j + c_{X_j^2 X_k} X_j^2+ c_{X_j^3 X_k} X_j^3+ 2 c_{X_j^2 X_k^2} X_j^2 X_k) \delta_{k,q}+ ( 2 c_{X_j^2 X_k} X_j X_k+ 3 c_{X_j^3 X_k} X_j^2 X_k) \delta_{j,q} + \sum \limits_{j \neq k \neq m} c_{X_j X_k X_m} X_j X_m \delta_{k,q} + c_{X_j^2 X_k X_m} (X_j^2 X_m \delta_{k,q}+2 X_j X_k X_m\delta_{j,q}) + \sum \limits_{j \neq k \neq m \neq l} c_{X_j X_k X_m X_l} X_j X_m X_l \delta_{k,q}$.

Consequently,
$x=0 \Rightarrow c_{X_k}=0$.
$\sum_k x_k =1$ is splitted into 2 cases. $x_q=1$ and $x_q=0$
$x_q=1 \Rightarrow 2 c_{X_q^2} + 3 c_{X_q^3} + 4 c_{X_q^4} = 0$ together with $c_{X_k^2} + c_{X_k^3} + c_{X_k^4}=0$ that lead to $c_{X_k^3}= -2 c_{X_k^2}, c_{X_k^4}= c_{X_k^2}$
$x_q=0 \Rightarrow c_{X_j X_q} + c_{X_j^2 X_q} + c_{X_j^3 X_q}=0, \forall j,q$.
$\sum_k x_k =2$ split again into the same cases.
$x_q=1 \Rightarrow 2 c_{X_j^2 X_q^2} + 2 c_{X_q^2 X_j } +3 c_{X_q^3 X_j }= 0$ together with $c_{X_j X_q} + c_{X_j^2 X_q} + c_{X_j^3 X_q}=0$ and $c_{X_j X_k} + c_{X_j^2 X_k}+ c_{X_j^3 X_k}+ c_{X_j^2 X_k^2}=0$ that lead to $c_{X_j^2 X_q^2}= 0, c_{X_q^2 X_j} = -3 c_{X_q X_j}, c_{X_q^3 X_j}= 2 c_{X_q X_j}$.
$x_q=0 \Rightarrow c_{X_j X_m X_q} + c_{X_j^2 X_m X_q} + c_{X_m^2 X_j X_q}= 0$. The last condition counted over triplet lead to Robinson perturbation term $c_{X_j^2 X_m X_q}= c_{X_j X_m^2 X_q} = c_{X_j X_m X_q^2}= - \frac{1}{2} c_{X_j X_m X_q}$

Combining all conditions together we get
$f(x)= \sum_k c_{X_k^2} X_k^2(X_k-1)^2 +\sum \limits_{j \neq k} c_{X_j X_k} ( X_j X_k - X_j^2 X_k- X_j^2 X_k+X_j^2 X_k^2)+ \sum \limits_{j \neq k \neq m} c_{X_j X_k X_m}(-2 X_j X_k X_m + X_j^2 X_k X_m +X_j X_k^2 X_m +X_j X_k X_m^2)+ \sum \limits_{j \neq k \neq m \neq l} c_{X_j X_k X_m X_l} X_j X_k X_m X_l .$

Now we need to analyze the possible values of coefficients that guarantee positiveness of quartic polynomial.

To be continued.

## Hilbert-Robinson-Reznick-Blekherman positive polynomials

Reznick (2007) (see previous post) simplified Robinson simplification of Hilbert construction of positive polynomials that are not sums of squares by his perturbation lemma. Blekherman shows that the mystery is in the dimension of monomial basis. For example, there are $2^n$ points in n-dimensional hypercube, but since there are only $\frac{(n+1)n}{2}$ quadratic monomials all this points when evaluated cannot have rank more then the number of monomials. As a consequence, it is sufficient to nullify only about quaratic number of points in a quadratic form (by applying a set of linear constraints on the coefficients arising from evaluations of values of monomials) to nullify all points in a hypercube for these quadratic forms.

There are much more monomials in quartic polynomials (much larger basis), and therefore much larger freedom in choosing coefficients such that quartic will be nullified at quadratic number of points in hypercube, but will be nonzero on other points of a hypercube! That lead that such quartic polynomial even if it will be positive will not be a sum of squares.

Reznick perturbation lemma open a way to automatically (algorithmically) generate positive polynomials that a re not sums of squares, which in the current version may not lead to sufficient expansion of positive polynomial cone to solve all the problems from a given class. Reznick (2007) perturbation lemma, simplified for our current purpose, in high school terms, starts from a sums of squares of terms defining hypercube, say $\{0,1\}^n$ is $f(x)= \sum \limits_{k=1}^N x_k^2(x_k-1)^2$. Moreover, at the minimum it round, i.e. Hessian is strictly positive definite (easy to check by direct calculations, intuitively each term in the sum around the minimum is a positive definite quadratic multiplied by approximately 1). Now we are going to perturb this quartic by another quartic ($g(x)$), splitting points in the hypercube into two sets. In one set we require that Taylor expansion of $g(x)$ vanish to second order term, and on the other set we require that $g(x)$ is strictly positive. Only those points in the hypercube are dangerous, since perturbation $f(x)+ c g(x), c>0$ may lead to negative values around minima for any positive $c$. In the rest of the space we can choose small enough $c$ to ensure positiveness of resulting polynomial (I skip this part, but one need to have worst estimate for the values of $g(x)$ for a given norm of $x$ and take a region bounded by some norm and outer region where only ratios between leading coefficients matter). For the first set of points $g(x)$ has Hessians with the finite eigenvalues. If we need to ensure that c times minimum eigenvalue is smaller that Hessian eigenvalues (all the same) for $f(x)$ in the minima. That ensures 0 value on the set that are local minima. For the second set of points the value is positive in some neighborhood by construction.

Now automatic construction: given monomial basis we need to ensure about quadratic number of points to have 0 values and gradients being 0. That is about $n^3$ conditions for about $n^4$ monomials. The rest of points in the hypercube should be strictly greater than zero. For that we need to ensure that the values at the basis points are positive and that all point in the hypercube are represented by the linear combinations with positive coefficients. For that we need to peak as the basis points the points with minimum number of ‘1’ as coordinates. and the second condition is the inequality condition. leading to linear program. It has solution because we have coefficients in front of $x_k^2$ that can grow unbound, and being compensated by other terms. and inequality condition is much weaker then equality condition. Then one can compute the estimate for the constant c, which depends only on the calculations in the basis points. The exact machinery still need to be worked out, since one need also estimate the values of projections of all point of hypercube onto basis points.

That may be not sufficient to produce wide enough expansion of SOS cone to solve all instances of, say, partition problem, but we may need small enough extension to pertube problem quartic to be represented by the sums of squares.

Sincerely yours,
C.T.

PS
psd that is not SOS:
$x_1^2 (x_1 - 1)^2 + x_2^2 (x_2 - 1)^2 + x_3^2(x_3 - 1)^2 + \frac{1}{1000} \left( 3 x_2 (x_2 - 1) ( 28 x_1^2 - 28 x_1 - 19 x_2^2 + 19 x_2 + 28 x_3^2 - 28 x_3) + 140 x_1 x_2 x_3 (x_1 + x_2 + x_3 - 2)\right)$

and the (not cleaned) code in Matlab with symbolic toolbox to get it

 %% mupad test for positive polynomials Hilber-Reznik n=3;

 y= evalin( symengine, sprintf( 'combinat::compositions(4, Length= %d, MinPart=0)', n+1) ); pow= arrayfun( @(k) double(y(k)), 1:numel(y), 'UniformOutput', false ); pow= cat(1, pow{:}); xs= sym( 'x', [n,1]); xx= zeros( 2^n, n ); v=0:2^n-1; for k=1:n, xx( bitand(v, 2^(k-1) )~=0 , k )=1; end %xx= 2*xx-1; xx(:, n+1)=1; %xx( end+1, :)= [1 2 2 1]; y= evalin( symengine, sprintf( 'combinat::compositions(2, Length= %d, MinPart=0)', n+1) ); pow2= arrayfun( @(k) double(y(k)), 1:numel(y), 'UniformOutput', false ); pow2= cat(1, pow2{:}); yy2= nan( size( pow2,1), size(xx,2) ); yy= nan( size( pow,1), size(xx,2) ); for k=1:size(xx,1), yy(:, k)= prod( bsxfun( @power, xx(k,:), pow ), 2); yy2(:, k)= prod( bsxfun( @power, xx(k,:), pow2 ), 2); end for k=size( pow, 1 ):-1:1, xsm( k )= sym(1); for k2= n:-1:1, xsm( k )= xsm( k )*xs(k2)^pow( k, k2 ); end end for k= n:-1:1, dxsm(k,:)= diff( xsm, xs(k) ); end r= rank(yy2); x0Idx= 1:7; x1Idx= 8; %we need also condition for gradient here dpow= zeros(size(pow)); dpow(:,end)=1; for k=1: size( pow, 2)-1, idx= pow(:,k)>0; dpow( idx, end )= dpow(idx, end).*pow(idx,k); dpow(idx,k)= pow(idx,k)-1; end % % % equality constraints lc= zeros(size(pow, 1), 0); for k=1:7, lc(:, end+1)= subs( xsm, xs, xx(k, 1:3) )'; lc(:, end+(1:n))= subs( dxsm, xs, xx(k, 1:3) )'; end % lc(:, end+(1:n))= subs( dxsm, xs, xx(8, 1:3) )'; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % The following line is a place to play with different polynomials % we have rather strange way to do it here by imposing eight point % where quartic polynomial vanishes first order term on Taylor expansion, % and the value at this point is positive (it is sufficient to have 0 here, % but the code would be more complicated). % removing second line below (lc .. ) and switching next lc lines % (commenting/ uncomenting) lead to Robinson polynomial % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% x2= [3 -3 3]; % [3 -1 3] also works well lc(:, end+(1:n))= subs( dxsm, xs, x2 )'; % comment for Robinson bc= zeros( size( lc, 2), 1 ); % lc(:, end+1)= subs( xsm, xs, xx(8, 1:3) )'; % uncomment for Robinson lc(:, end+1)= subs( xsm, xs, x2 )'; % comment for Robinson bc(end+1)=1; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% cf= mldivide( lc', bc)*54*2 % multiplier 1 for Robinson disp( [size(lc) rank(lc)]) % % 

% coefficient c in perturbation lemma was found by hand, and in now way is optimal p2= 1/1000*sum( round(cf).*xsm.') + sum( xs.^2.*(xs-1).^2) % first factor is 1 for Robinson dp2= [diff(p2, xs(1)) diff(p2, xs(2)) diff(p2, xs(3))] subs( p2, xs, xx(8, 1:3)) sol= solve(dp2) xv= ([sol.x1 sol.x2 sol.x3]); vf= arrayfun( @(k) double(subs( p2, xs, xv(k, :))), 1:size(xv,1))'; [min(vf) min(real(vf)) min(imag(vf))] 

Posted in Uncategorized | 1 Comment

## P vs NP – an analogy between analogies

There are few ingredients that  may allow to prove that P=NP, although most people believe in opposite. Here I draw outline.

1. Partition problem: given multiset $a$ with $n$ entries tell whether it is possible to divide it into two miltisets having the same sum. Formally, tell whether there exists vector $x \in \{-1,1\}^n$ such that $\sum \limits_{k=1}^n a_k x_k=0$, or in vector notation $x^T a=0$. This problem is NP-complete.

2. It is possible to encode this problem into minimization of quartic polinomial:
$\mathop{\mbox{min} } \limits_{x \in \mathbb{C} } \sum \limits_{k=1}^n \left( x_k^2-1\right)^2+ \left( \sum \limits_{k=1}^n a_k x_k \right)^2$
The minimum is zero when $x$ exists and is greater than zero otherwise. Moreover, non-zero value is inversely bounded by length of the vector $a$.

3. Non-zero minimum exists if $\exists \lambda_k \geq 0, \gamma >0 | \sum \limits_{k=1}^n \left( x_k^2-1\right)^2+ \left( \sum \limits_{k=1}^n a_k x_k \right)^2 = \sum \lambda_k \mbox{PSD}_k(x) +\gamma$, where $\mbox{PSD}(x)$ is positive semidefinite polynomial ( a polynomial that is non-negative over whole range of values $x$ ), and summation is taken over all PSD.

4. Set PSD polynomials is convex. Therefore, in principle it is solvable in polynomial time. The problem is the generation of rays of positive polynomials. For instance it is easy to generate rays of PSD polynomials consisted of sum squares of polynomials. On the other hand there are plenty of examples of PSD polynomials that are not sum of squares (see for example Reznick, 2007). It is not easy to find all of them.

5. There is a finite basis for polynomials of a fixed degree (4 in this case, Wikipedia) consisting of linear combination of all possible monomials. So there are not too many (polynomial in the number of inputs) basis function that can be used to show non-zero minimum. The question how to generate them.

6. Computer Science PSD: this are PSD that are instances of Computer Science problems having no solution, for example, Partition problem polynomials from (2). For instance, polynomial corresponding to $a= [1, 1, 1, 1, 1]$ is strictly positive. Here we need to generate enough PSD that certainly have no solution. Then we would have a complete basis for PSD polynomials and solve the problem, which would be an instance of linear programming in this case (details for similar problem can be found in Parrilo, 2000, thesis).

7. Partition problem has a nice property of a phase transition (Mertens, 2003). For instance, there is a specific parameter, that when problem is below this parameter probability to obtain solution is 1, and when it is above the probability of perfect partition is 0 for large $n$. Therefore, we have a tool to generate many examples of strictly positive polynomials, and hopefully get a complete basis of positive polynomials with probability tending to 1.

Therefore, we use (7) to generate basis (2), and solve linear program problem in (3). There are high chances that we get certificate for unsolvable problem with probability close to 1 in polynomial time.

## Lonely Runner Conjecture. General case.

We consider (LRC) .

Conjecture Suppose $n>1$ runners having distinct constant speeds $v_k > 0$ start at a common point (origin) and run laps on a circular track with circumference 1. Then, there is a time when no runner is closer than $\frac{1}{n+1}$ from the origin.

W.l.o.g. we can assume $v_k > v_m \forall k>m$.

One can formulate LRC as follows. Suppose $l_k \in \mathbb{N}_0$ is the number of whole laps (including 0) runner k passed on a track, than $\exists t \in \mathbb{R}_+$ and $\exists l_k | l_k+\frac{ 1 }{n+1} \leq v_k t \leq l_k+ \frac{n}{n+1}$.

Case n=1, two runners is trivial. At time $t=\frac{1}{2 v_1}$ runner 1 is exactly distance $\frac{1}{2}$ ($l_1= 0$).

Case n=2, three runners is a special case.

$\left\{ \begin{array}{ll} \frac{l_1+1/3}{v_1} \leq t, & t \leq \frac{l_1+2/3}{v_1} \\ \frac{l_2+1/3}{v_2} \leq t, & t \leq \frac{l_2+2/3}{v_2} \end{array} \right.$

Since $t \in \mathbb{R}_+$ we can eliminate it if all combination of left parts on the left columns are smaller than any right parts in the right column of the table. e.g.
$\left\{ \begin{array}{l} \frac{l_1+1/3}{v_1} \leq \frac{l_1+2/3}{v_1} \\ \frac{l_1+1/3}{v_1} \leq \frac{l_2+2/3}{v_2} \\ \frac{l_2+1/3}{v_2} \leq \frac{l_1+2/3}{v_1}\\ \frac{l_2+1/3}{v_2} \leq \frac{l_2+2/3}{v_2} \end{array} \right.$

The first and the last inequality are trivially correct. From the second and third inequality we would like to express $l_2$
$\frac{v_2}{v_1} \left( l_1 + \frac{1}{3} \right) -\frac{2}{3} \leq l_2 \leq \frac{v_2}{v_1} \left( l_1 + \frac{2}{3} \right) -\frac{1}{3}.$
In other words,
$\frac{v_2}{v_1} \left( l_1 + \frac{1}{3} \right) -\frac{2}{3} \leq l_2 \leq \frac{v_2}{v_1} \left( l_1 + \frac{1}{3} \right) -\frac{2}{3} + \frac{1}{3}\frac{v_2}{v_1} +\frac{1}{3}.$

There are 2 sub-cases.

1. Sub-case $\frac{v_2}{v_1} \geq 2.$
$\frac{1}{3}\frac{v_2}{v_1} +\frac{1}{3} \geq 1$ and $\exists l_2 \in \mathbb{N}_0$ satisfying inequality
2. Sub-case $\frac{v_2}{v_1} < 2 .$
In this case $l_1=l_2=0$ lead to (remeber that $\frac{v_2}{v_1} > 1$ )
$\frac{1}{3} \frac{ v_2}{v_1} - \frac{2}{3} \leq 0 \leq \frac{2}{3} \frac{v_2}{v_1} - \frac{1}{3}.$

Case n=3, four runners is an illustration for a general case.

$\left\{ \begin{array}{ll} \frac{l_1+1/4}{v_1} \leq t, & t \leq \frac{l_1+3/4}{v_1} \\ \frac{l_2+1/4}{v_2} \leq t, & t \leq \frac{l_2+3/4}{v_2} \\ \frac{l_3+1/3}{v_3} \leq t, & t \leq \frac{l_3+3/4}{v_3} \end{array} \right.$

Let’s express $l_2$ in terms of $l_1$
$\frac{v_2}{v_1} \left( l_1 + \frac{1}{4} \right) -\frac{3}{4} \leq l_2 \leq \frac{v_2}{v_1} \left( l_1 + \frac{3}{4} \right) -\frac{1}{4}.$
Rewriting it we obtain
$\frac{v_2}{v_1} \left( l_1 + \frac{1}{4} \right) -\frac{3}{4} \leq l_2 \leq \frac{v_2}{v_1} \left( l_1 + \frac{1}{4} \right) -\frac{3}{4} + \frac{1}{2}\frac{v_2}{v_1} +\frac{1}{2}.$
$\frac{1}{2}\frac{v_2}{v_1} +\frac{1}{2} >1,$ since $\frac{v_2}{v_1} > 1.$ In other words, $\forall l_1 \exists l_2 \in \mathbb{N}_0$ satisfying inequality.

Now, let express $l_3$ in terms of $l_1$ and $l_2$
$\left\{ \begin{array}{l} \frac{v_3}{v_1} \left( l_1 + \frac{1}{4} \right) -\frac{3}{4} \leq l_3 \leq \frac{v_3}{v_1} \left( l_1 + \frac{3}{4} \right) -\frac{1}{4} \\ \frac{v_3}{v_2} \left( l_2 + \frac{1}{4} \right) -\frac{3}{4} \leq l_3 \leq \frac{v_3}{v_2} \left( l_2 + \frac{3}{4} \right) -\frac{1}{4}. \end{array}\right.$

We can express $l_2$ with inequalities obtained earlier
$\left\{ \begin{array}{l} \frac{v_3}{v_1} \left( l_1 + \frac{1}{4} \right) -\frac{3}{4} \leq l_3 \leq \frac{v_3}{v_1} \left( l_1 + \frac{3}{4} \right) -\frac{1}{4} \\ \frac{v_3}{v_2} \left( \frac{v_2}{v_1} \left( l_1 + \frac{1}{4} \right) -\frac{3}{4} + \frac{1}{4} \right) -\frac{3}{4} \leq l_3 \leq \frac{v_3}{v_2} \left( \frac{v_2}{v_1} \left( l_1 + \frac{3}{4} \right) -\frac{1}{4} + \frac{3}{4} \right) -\frac{1}{4}. \end{array}\right.$
Collecting terms we obtain
$\left\{ \begin{array}{l} \frac{v_3}{v_1} \left( l_1 + \frac{1}{4} \right) -\frac{3}{4} \leq l_3 \leq \frac{v_3}{v_1} \left( l_1 + \frac{3}{4} \right) -\frac{1}{4} \\ \frac{v_3}{v_1} \left( l_1 + \frac{1}{4} \right) -\frac{3}{4} -\frac{1}{2} \frac{v_3}{v_2} \leq l_3 \leq \frac{v_3}{v_1} \left( l_1 + \frac{3}{4} \right)-\frac{1}{4}+ \frac{1}{2} \frac{v_3}{v_2}. \end{array}\right.$

We can see that first inequality is always stronger that the second one (meaning that if $l_3$ satisfies first inequalities it will satisfy second inequalities). But the first inequalities are the same as previous inequalities for $l_2$ with relabelling. Therefore, $\forall l_1 \exists l_2, l_3 \in \mathbb{N}_0$ satisfying initial inequalities and LRC holds.

General case

We start with $2 n$ inequalities

$\left\{ \begin{array}{lll} \frac{l_k+\frac{1}{n+1}}{v_k} \leq t, & t \leq \frac{l_k+\frac{n}{n+1}}{v_k} & k=1..n \end{array} \right.$

Now we expressing $l_{k+m_1}, m_1 \geq 1$ in terms of $l_k$ and $l_{k+m_2}, m_2 > m_1$ in terms of $l_{k+m_1}$ and $l_{k}.$
$\frac{v_{k+m_1}}{v_k} \left( l_k + \frac{1}{n+1} \right) -\frac{n}{n+1} \leq l_{k+m_1} \leq \frac{v_{k+m_1}}{v_k} \left( l_k + \frac{n}{n+1} \right) -\frac{1}{n+1}.$
$\frac{v_{k+m_2}}{v_{k+m_1}} \left( l_{k+m_1} + \frac{1}{n+1} \right) -\frac{n}{n+1} \leq l_{k+m_2} \leq \frac{v_{k+m_2}}{v_{k+m_1}} \left( l_{k+m_1} + \frac{n}{n+1} \right) -\frac{1}{n+1}.$
$\frac{v_{k+m_2}}{v_k} \left( l_k + \frac{1}{n+1} \right) -\frac{n}{n+1} \leq l_{k+m_2} \leq \frac{v_{k+m_2}}{v_k} \left( l_k + \frac{n}{n+1} \right) -\frac{1}{n+1}.$

Now we can substitute first inequalities into the second ones.
$\frac{v_{k+m_2}}{v_{k+m_1}} \left( \frac{v_{k+m_1}}{v_k} \left( l_k + \frac{1}{n+1} \right) -\frac{n}{n+1} + \frac{1}{n+1} \right) -\frac{n}{n+1} \leq l_{k+m_2} \leq \frac{v_{k+m_2}}{v_{k+m_1}} \left(\frac{v_{k+m_1}}{v_k} \left( l_k + \frac{n}{n+1} \right) -\frac{1}{n+1} + \frac{n}{n+1} \right) -\frac{1}{n+1}.$
Rearranging terms we obtain
$\frac{v_{k+m_2}}{v_k} \left( l_k + \frac{1}{n+1} \right) -\frac{n}{n+1} - \frac{n-1}{n+1} \frac{v_{k+m_2}}{v_{k+m_1}} \leq l_{k+m_2} \leq \frac{v_{k+m_2}}{v_k} \left( l_k + \frac{n}{n+1} \right) -\frac{1}{n+1} +\frac{n-1}{n+1} \frac{v_{k+m_2}}{v_{k+m_1}}.$
Compare it to
$\frac{v_{k+m_2}}{v_k} \left( l_k + \frac{1}{n+1} \right) -\frac{n}{n+1} \leq l_{k+m_2} \leq \frac{v_{k+m_2}}{v_k} \left( l_k + \frac{n}{n+1} \right) -\frac{1}{n+1}.$
The second inequality is always stronger.

Therefore, we left with the set of inequalities (when they are satisfied LRC holds when LRC holds they are satisfied!!! )
$\frac{v_{k}}{v_1} \left( l_1 + \frac{1}{n+1} \right) -\frac{n}{n+1} \leq l_{k} \leq \frac{v_{k}}{v_1} \left( l_1 + \frac{n}{n+1} \right) -\frac{1}{n+1},\ \forall k=2..n.$

Lets rewrite it again
$\frac{v_{k}}{v_1} \left( l_1 + \frac{1}{n+1} \right) -\frac{n}{n+1} \leq l_{k} \leq \frac{v_{k}}{v_1} \left( l_1 + \frac{1}{n+1} \right) -\frac{n}{n+1} + \frac{n-1}{n+1} \left( \frac{v_k}{v_1} +1 \right)$

$\frac{n-1}{n+1} \left( \frac{v_k}{v_1} +1 \right) > 2 \frac{n-1}{n+1} = 1+ \frac{n-3}{n+1} \geq 1$ if $n \geq 3 .$

It is not clear from this why $\frac{1}{n+1}$ is tight distance.

## On the lonely runner conjecture III

We consider (LRC) .

Conjecture Suppose $n>1$ runners having distinct constant integer speeds $v_k$ start at a common point (origin) and run laps on a circular track with circumference 1. Then, there is a time when no runner is closer than $\frac{1}{n+1}$ from the origin.

Case of $n=2,3$ runners is discussed here. Here we look at case $n=4$.

Let $\| x \|$ denote the distance of x to the nearest integer.

Case $v_k \mod 5 \neq 0,\ \forall k$. At time $t=\frac{1}{5}$ all runners are at least $\frac{1}{5}$ from the origin. Done.

Case $v_k= 5 r_k, k=1..3, v_4 \mod 5 \neq 0$. There is time $t_1$ such that runners $r_k, k=1..3$ are at least $\frac{1}{4}$ from the origin – see case $n=3$. At time $t_2= \frac{t_1}{5}$ runners $v_1, v_2, v_3$ are at the same positions as runners $r_1, r_2, r_3$ at time $t_1$. If at time $t_2$, $\| v_4 t_2\| \geq \frac{1}{5}$ we are done. Otherwise, since $v_4$ and 5 are co-prime, $\exists m : \| v_4 \frac{m}{5} \|=$ $\frac{2}{5} \Rightarrow$ $\| \frac{2}{5} - v_4 \left( t_2+\frac{m}{5} \right) \| \leq \frac{1}{5}$. Done.

Case $v_k= 5 s_k, k=1,2, v_k \mod 5 \neq 0, k=3,4$.

Definition Sector $S_k= \left( \frac{k}{5}, \frac{k+1}{5} \right), k=0..4$.
There is a time $t_1$ such that runners $s_k, k=1,2$ are at least $\frac{1}{3}$ from the origin – see case $n=2$. Since $v_k, k=3,4$ and 5 are co-prime those runners visit all sectors once at times $\frac{m}{5}, m=0..4$, and runners 1 and 2 will be at the same position. There 5 such times, during 2 times runner 3 will be at sectors $S_0, S_4$ and during 2 times runner 4 will visit the same sectors. Therefore, there is $m:\ \| v_k \left( \frac{t_1+m}{5} \right) \| > \frac{1}{5}$. Done.

Two previous cases follow from this post.
Now difficult case.

Case $v_1= 5 s_1,\ v_k \mod 5 \neq 0, k=2,3,4$.

Rearrange speeds that $v_2+v_3 = 5 s_2$. If there more than one way choose the one with maximum sum. We have 2 sub-cases: $s_1 \geq s_2$, $s_1< s_2$.

1. $s_1 \geq s_2$
$\exists m:\ \| v_2 \frac{m}{5} \|=\| v_3 \frac{m}{5} \| = \frac{2}{5}$. The runner 1 is faster than either runner 2 or 3. Therefore, they meet at distance greater than $\frac{1}{5}$.

Now runner 4.

1. $\| v_4 \frac{m}{5} \| = \frac{2}{5} \Rightarrow$ this runner is slower than either runner 2 or 3 (call this runner $r$) which is at the same position as runner 4. Therefore, it will meet runner 1 later than runner $r$, which meet runner 1 at distance larger than $\frac{1}{5}$. Done.
2. $\| v_4 \frac{m}{5} \| = \frac{1}{5} \Rightarrow$. This runner should move fast to reach runner 1 at distance $\frac{1}{5}$. So, it will cover at least $\frac{3}{5} + l$ of the lap. Then, looking at opposite direction in time in the same time it will cover the same distance, and will be at least $\frac{2}{5}$ from the origin when runner 1 reach distance $\frac{1}{5}$ If it is moving even faster to meet runner 1 at $\frac{1}{5}$ it will miss runner 1 from the opposite side. Namely, it has to cover at least the whole lap, and therefore meet runner 1 at the opposite side before runner 1 reaches $\frac{1}{5}$. Done.
2. $s_1< s_2$ This is the most interesting case.

At times $t=\frac{m}{5s_2}, m=1..5s_2-1$ runners 2 and 3 are the same distance from the origin on the opposite sides from the origin.

Runner 1 exhibit repeated motion at $t$. It makes $5 \gcd ( s_1,s_2)$ cycles, where $\gcd$ stands for greatest common divisor. The number of different positions it attain evenly distributed along the track is $n_1=\frac{s_2}{\gcd ( s_1,s_2)} \geq 2$. If $n_1=2$ half of the time runner 1 is away from the origin. With larger $n_1$ there is bigger fraction, with the limit $\frac{3}{5}$. Let $t_1 \in t$ is the time when runner 1 is distant. At the same time runners 2 and 3 same distance on the opposite sides from the origin. Now at times $t_1+\frac{m}{5}, m=0..4$ runner 1 stays at the same position, runners 2 and 3 are on the opposite position relative to the origin, and runner 4 visiting all sectors once each time. Therefore, there are total 2 moments when runner 4 in $S_0, S_4$, and there are total, possibly different 2 times runner 2 in $S_0, S_4$, on the other hand when runner 2 in sector 0 runner 3 is in sector 4 and vice verse. Therefore, there is $m:\ \| v_k \left( t_1 + \frac{m}{5} \right)\| \geq 1$. Done.

$\blacksquare$

PS. If you find error or better exposition leave comment. If you do not want to be in the list of those talking to crackpot trisector, leave a note in the comment, the comment will not appear public, but the content will be implemented in the text.

PPS. There is a much shorter prove for $n=4$ in Barajas and Serra(2008). Algebraically it is short, but I think it lucks an intuition. I have filling this is quite general approach, and cases $n=5$ and $n=6$ bring new ingredients (non prime $n+1$, and competition between 2 pairs of paired runners ). May be we need to wait for the new ingredient until $n=3 \times 5 -1 = 14$.

Posted in Uncategorized | 1 Comment

## On the lonely runner conjecture II

We consider (LRC) .

Conjecture Suppose $n>1$ runners having distinct constant integer speeds $v_k$ start at a common point (origin) and run laps on a circular track with circumference 1. Then, there is a time when no runner is closer than $\frac{1}{n+1}$ from the origin.

We first show trivial proves for $n=2,3$ runners.

Let $\| x \|$ denote the distance of x to the nearest integer.

Let $\kappa_n = \inf \max \limits_{0 \leq t \leq 1} \min \limits_{ 1 \leq i \leq n} \| v_i t \|$. where the infimum is taken over all n-tuples $v_1, ... v_n$ of distinct positive integers.

In terms of $\kappa_n$ the LRC state that $\kappa_n= \frac{1}{n+1}$

Without loss of generality (wlog) we can assume $k < m \Leftrightarrow v_k < v_m$.

Case $n=2$. Wlog we can assume $v_1, v_2$ are relatively prime. At time $t_k= \frac{m}{v_1+v_2}, m=1..v_1+v_2-1$ two runners are at the same distance from the origin from different sides of the lap at distances proportional to $\frac{1}{v_1+v_2}$. Since they are relatively prime both runners visit all the points $\frac{m}{v_1+v_2}, m=1..v_1+v_2-1$. The largest distance is $\frac{ \left[ \frac{v_1+v_2}{2} \right] }{v_1+v_2}$, where $\left[ \circ \right]$ means integer part.

For example, $v_1=1, v_2= 2$, at times $\frac{1}{3}, \frac{2}{3}$ runners are at positions $(\frac{1}{3}, \frac{2}{3})$ and $(\frac{2}{3},\frac{1}{3})$ and the maximum distance from origin is $\frac{\left[ \frac{1+2}{2}\right]}{3}= \frac{\left[1.5 \right]}{3}= \frac{1}{3}$.

Another example, $v_1= 2, v_2= 3$, the maximum distance is $\frac{2}{5} > \frac{1}{3}$.

If $v_1, v_2 \mod 2 =1$ the maximum distance is $\frac{1}{2} > \frac{1}{3}$ at time $\frac{1}{2}$.

In general the maximum distance is $r_{1,2}= \frac{1}{2} \left(1- \frac{ (v_1+v_2) \mod 2 }{ v_1+v_2} \right)$ with the minimum for runners at speeds $v_1= 1, v_2= 2$. Therefore, $\kappa_2= \frac{1}{3}$.

Case $n=3$.

• First we assume simple case: $v_3 \mod ( v_1+v_2 )= 0$, e.g $v_3= q(v_1+v_2), q \in \mathbb{N}_+$.

At times $t= \frac{m}{v_1+v_2}$ runner 3 is at the origin. There is a time such that some time before it was the same distance with runner 1 and some time after it will be the same distance with runner 2. (The situation is reversed at times $1-t$). We are interested when that is happening for the time runners 1 and 2 are most distant from the origin.

For runners 1 and 3: They need to pass $r_{1,2}$ with speed $v_1+v_3$, so the time needed is $\frac{r_{1,2} }{v_1+v_3}$. Runner 3 passes $r_{1, 3}= \frac{v_3 r_{1,2} }{v_1+v_3}= r_{1,2} \frac{1}{1+v_1 / v_3 }$. Therefore, the closest point is reached when $\frac{v_1}{v_3}= \frac{v_1}{t (v_1+v_2) }$ is maximum.

$r_{1, 3}= \frac{q ( v_1+v_2 ) }{v_1+ q ( v_1+v_2 ) } \frac{1}{2} \left(1- \frac{ (v_1+v_2) \mod 2 }{ v_1+v_2} \right)$

If $(v_1+v_2) \mod 2 = 0$, $r_{2, 3} < r_{1, 3}$ around $r_{1,2}= \frac{1}{2}$

$r_{2, 3}= \frac{1}{2} \frac{q ( v_1+v_2 ) }{v_2+ q ( v_1+v_2 ) }$

Lemma 1. $\frac{q ( v_1+v_2 ) }{v_2+ q ( v_1+v_2 ) } > \frac{1}{2}$.
Proof. $\frac{q ( v_1+v_2 ) }{v_2+ q ( v_1+v_2 ) } - \frac{1}{2} =$ $\frac{1}{2} \frac{ 2 q ( v_1+v_2 ) - v_2 - q ( v_1+v_2 )}{v_2+ q ( v_1+v_2 ) } =$ $\frac{1}{2} \frac{ q v_1 + ( q - 1) v_2 }{v_2+ q ( v_1+v_2 ) } > 0$ $\blacksquare$

Now, consider the case when $(v_1+v_2) \mod 2 = 1$.

$r_{1, 3}= \frac{1}{2} \frac{q ( v_1+v_2 ) }{v_1+ q ( v_1+v_2 ) } \frac{ v_1+v_2 - 1 }{ v_1+v_2} = \frac{1}{2} \frac{q ( v_1+v_2 - 1 ) }{v_1+ q ( v_1+v_2 ) }$

Lemma 2. $\frac{q ( v_1+v_2 - 1 ) }{v_1+ q ( v_1+v_2 ) } \geq \frac{1}{2}$
Proof. $\frac{ ( v_1+v_2 - 1 ) }{v_1/q + v_1+v_2 } - \frac{1}{2} =$ $\frac{2 v_1+ 2 v_2 - 2 - v_1/q - v_1-v_2 }{2 \left[ v_1/ q+ ( v_1+v_2 ) \right] } =$ $\frac{ v_1 \left( 1- \frac{1}{q} \right)+ v_2 - 2 }{2 \left[ v_1/ q+ ( v_1+v_2 ) \right] }$. Since $v_2 \geq 2$ nominator is greater than 0, except when $v_2=2, v_1= 1, q= 1$ $\blacksquare$

Corollary 3. $r_{1, 3} \geq \frac{1}{4}$.
Corollary 4. $r_{1, 3} = \frac{1}{4}$ only for $v_1=1, v_2=2, v_3=3$.

• Case: $v_3 \mod ( v_1+v_2 ) \neq 0$.

Lemma 5. Fix time $t= \frac{m}{v_1+v_2}, m \in \{1, ..., v_1+v_2-1 \}$. Let $r_3$ be the distance from the origin of runner 3 at the moment $t$ and $r_{1,2} > r_3$ be the distance of the runners 1 and 2 from the origin at the same time. The maximal distance when runners 1 and 2 or 1 and 3 equidistant around time $t$ is greater than $\frac{r_3+r_{1, 2}}{2}$.
Proof. Either the runner 3 is running toward or away from the origin. e.g. the distance to the origin either decrease with time or increase. Let $v$ be the speed of the runner 1 or runner 2 moving in opposite direction, so that the difference in distances is decreasing moving either forward or backward in time. Since $v_3 > v$ runner 3 will cover greater distance away from the origin that other runner $\blacksquare$

Lemma 6. Fix the time $t= \frac{m}{v_1+v_2}$ when $r_{1,2}= \frac{1}{2} \left(1- \frac{ (v_1+v_2) \mod 2 }{ v_1+v_2} \right)$. Let $r'_3= \frac{m v_3 \mod (v_1+v_2) }{v_1+v_2}$, and $r_3= \min (r'_3, 1-r'_3)= \| r'_3\|$ – distance of runner 3 from the origin. $r_{1, 2} + r_3 > \frac{1}{2}$.
Proof. $r_3 \geq \frac{1}{v_1+v_2}$, $r_{1,2}+r_3 \geq \frac{1}{2} \left(1- \frac{ (v_1+v_2) \mod 2 }{ v_1+v_2} \right) + \frac{1}{v_1+v_2} =$ $\frac{1}{2} + \frac{2- (v_1+v_2) \mod 2 }{v_1+v_2} > \frac{1}{2}$ $\blacksquare$

Combining Lemma 5 and Lemma 6 shows $\max (r_{1,3}, r_{2,3}) > \frac{1}{4}$.

Overall, $\kappa_3= \frac{1}{4}$ only for runners $v_1=1, v_2=2, v_3=3$.

Posted in Uncategorized | 1 Comment

## Cantor diagonal argument is almost surely inconsistent

Here we construct table consisted of realization of Bernoulli processes; using Cantor diagonal argument we construct row that is not in the table, and finally we show that constructed number is almost surely in the table countably infinite number of times.

Consider doubly infinite table $X_{k,m}$, where index $k \in \mathbb{N}$ enumerates rows, and index $m \in \mathbb{N}$ enumerates columns. Each element $X_{k,m}$ is independent binary random variable with equally probable possible states $0$ and $1$. Suppose $x_{k,m}$ is a realization of random variables. We are going to fix it for the rest of the post.

Cantor diagonal argument Let row $y_{k} = 1-x_{k,k}$. Since, $y$ is different from every row in at lest one place it is not in the table. Using induction we will check the next row diagonal, and will get proof by induction .

Theorem There are countably many rows equal to $y$ in the table with probability 1.
Proof 1. Select the subset of rows ($x_{k,\circ}$) where the first column has value $y_1$: $A^1=\{ x_{k,\circ} | x_{k,1}= y_1 \}$. Since $x_{k,m}$ is a realization of independent random variable, there are infinite number of rows in $A^1$ with probability one. Moreover, viewing $A^1$ as a table one can see that $a_{k,1} = y_1, \forall k$, and $a_{k,m}, m>1, \forall k$ is a realization of equi-probable binary random variable.

Induction step. Suppose there is a set of countable many rows $A^k$ such that $a_{p,m}^k= y_m, \forall m<=k, \forall p$. We select from the table $A^k$ a subset of rows that have $A^{k+1}= \{ a^k_{p, \circ} | a^k_{p,k+1}=y_{k+1} \}$. The set $A^{k+1}$ consists of countable infinite number of rows with probability 1. Moreover, the table $A^{k+1}$ divided into 2 parts. The left part- columns from 1 to $k+1$ – all rows coincide with $y_1 ... y_{k+1}$. The right part – all columns starting from $k+2$ are realization of independent random variable.

Therefore, by induction, there is set “$A^{\infty}$ that is countably infinite with probability 1, and each member consists of rows $y$. QED.

If one interpret table $x_{k,m}$ as membership table, e.g. a set $B_{k}= \{ e_m : x_{k,m} =1 \}$ than we have countable infinite representation of power set of countably infinite set by the theorem, whereas Cantor diagonal argument says the opposite. Therefore, if one replace the axiom of choice with the axiom of “free will’ – there exist Bernoulli process one have contradictory statement about sets cardinality. Axiom of choice is than deductible from the fact that all members of the sets $A^k$ are ordered by the rows and particular implementation of random variables.

Applying weights to the column, e.g. representing real numbers $r=\sum x_{k,m} 2^{-m}$ shows there are countable many reals, and moreover there are countable many equal reals.

Posted in Uncategorized | 1 Comment

## Nullspace of tautologies

Below is Mathematica printout showing the usefulness of tautologies.
tautologies6vars4thOrder

Given $x_k, k=1..6$ and equations $x_k^2-1=0$, one can expact 64 dimensional nullspace in the space of monomials of some degree. The above show that in the usual Nullstellensatz case one need 8th order monomials, whereas it is sufficient to have tautologies variables of equivalent degree 6. This is on decoding side.

The encoding (problem equations) side still need some work to be done. What is obvious is that there is much more than just multiplication by a monomials. For example, take quadratic encoding polynomial $f= \sum a_{i,k}, x_i x_k = 0, x_0= 1$. In tautology variables it is linear equation, but than one can split it into two halves on the right and left side and square it. One can also take cubes, that is still possible since we are looking at equivalent 6th order polynomials. One has exponentially many ways to split encoding equation. The question here how to extract relevant information in, say, polynomial time.

## NP-complete problems and tautologies

Many NP complete problems can be encoded in system of polynomial equations. For example, in partition problem one is asking whether it is possible to divide a list of integers into two lists that the sum of element of each least are equal. Given the list of elements $a \in \mathbb{Z}^n$ one is looking for the element $x \in \{ \pm 1 \}^n$, such that $\sum \limits_{k=1}^n x_k a_k =0$.

To encode the problem into the system of polynomial equations over $\mathbb{C}$ one need $n$ equations of the form $x_k^2-1=0$ – that will ensure variables $x_k=\pm 1$, and the above mentioned equation $\sum \limits_{k=1}^n x_k a_k =0$. In total $n+1$ nonlinear equations. We can also change the variables that $x'_k= \frac{x_k+1}{2} \in \{0,1\}$. In some sense this variables may be easier for the analyses later.

One way to solve this equation is to linearise it, e.g. we define a new set of variables $y_{(k,m)}= x'_k x'_m,\ k,m=0..n$, and we set $x'_0=1$. Now in terms of $y_{(k,m)}$ we have system of linear equations. Unfortunately, we have lost relationship between terms. Linear system does not “know” that $y_{(2,3)}= y_2 y_3$, etc. On the other hand, if solution of the original system exists it should lay in the null space of the coefficient matrix. We will try use it. Suppose, we have null space $U=[u_1,..., u_K] \in \mathbb{C}^{ \frac{(n+1)(n+2)}{2} \times K }$, than if system of equations has the solution all monomials will be simultaneously expressed as a linear combination of null space vectors $y_{(k,m)}(c)= \sum \limits_{i=1}^K c_i u_{i,(k,m)}$. The dimensionality of null space $K$ is exactly the number of quadratic monomials minus number of equations.

So far, we were looking only at second order monomials. If we go to higher order monomials we can see that $x_{k_1} x_{k_2} x_{k_3} x_{k_4}= (x_{k_1} x_{k_2}) (x_{k_3} x_{k_4})=(x_{k_1} x_{k_3}) (x_{k_2} x_{k_4})=(x_{k_1} x_{k_4})( x_{k_2} x_{k_3})$. What we wrote is tautology – this is true independent of the values of $x_k$. This is also true for any $k_1,...,k_4$. So this tautologies can be written in terms of our new variables $y_{(k_1,k_2)}y_{(k_3,k_4)}-y_{(k_1,k_3)}y_{(k_2,k_4)}=0$, $y_{(k_1,k_2)}y_{(k_3,k_4)}-y_{(k_1,k_4)}y_{(k_2,k_3)}=0$. On the other hand, if we have $k_m = k_n \forall m \neq n$, than we does not have tautology. In any case, we can write down all tautologies for up to order 4, and their expression in terms of new variables $y$. Moreover, for each $y_{k,m}$ we have its linear expression in terms of unknowns $c_i$. So if we expand tautologies in terms of $c_i$ we will get a new set of quadratic equations, that must be satisfied, if original system has a solution.

Now we already know what to do. We need to linearise the system of quadratic equations, for which we need to introduce new variables $b_{k,m}= c_k c_m$, write down the system of linear equations, find the null space of coefficient matrix, encode $b_{m,k}$ as a linear combination of the null space basis, and finally encode forth-order monomials in terms of new coefficient of new null space basis. Ok, we can repeat this forever, just remember to write down all quadratic tautologies in terms of known monomials (e.g. $(x_1x_2x_3x_4)(x_5x_6x_7x_8)= (x_1x_2x_3x_5)(x_4x_6x_7x_8)=...$ many more tautologies). What is interesting here is how $K$ changes with iterations.

Ok, I will come back here later, when I cool down and wil have more time. Note that the number of tautologies are much more (seems to be exponentially more) than the number of monomials.

Each iteration we are squaring the number of variables which encode monomials in terms of null space. Now consider only monomials with $k_m \neq k_n, \forall m \neq n$. If we have monomial of degree $2k$ than only for that monomial we have $\frac{1}{2}\binom{2k}{k}$, since we want to choose half variables, and one half comes from the fact that multiplication is commutative. The number of monomials is $\binom{n}{2k}$. So, assuming tautologies are linearly independent, we have $K_0=n^2$, $K_{m+1}=K_m^2-\frac{1}{2}\binom{2m}{m}\binom{n}{2m} =$ $K_m^2-\frac{1}{2}\binom{n-m}{m}\binom{n}{m} \approx$ $K_m^2-\frac{1}{2} n^{2m}/m!$. So the lower bound is asymptotically …

Posted in Uncategorized | 2 Comments

## Semiprime factorization and custom proof system

Suppose we have $N=pq$, with $p$ and $q$ are unknown odd primes. We can encode factorization problem in the system of polynomial equations. For instance, $p= 1+ \sum_{k=1}^n 2^k x_k$, $q= 1+ \sum_{k=1}^n 2^k y_k$, where $n = \lfloor \log_2 N \rfloor$ is one less the number of bits required to represent $N$, and $x_k, y_k$ are binary indeterminates. By abuse of notation, we can write the following system of equations (here $x, y \in \mathbb{C}^n$)

$\left\{ \begin{array}{lll} f_1= &x_k^2-x_k & =0 \\ g_1= &y_k^2-y_k &=0 \\ h_{1,1}= &\left( 1+ \sum_{k=1}^n 2^k x_k \right) \left( 1+ \sum_{k=1}^n 2^k y_k \right) -N & = 0 \end{array} \right.$

This system has only two solutions for semiprimes – $x$ encoding $p$, $y$ encoding $q$, and vice versa. Therefore, the Groebner basis will consist of $2n$ linear equations encoding line passing through $(x,y)= (p,q)$ and $(x,y)=(q,p)$, and one quadratic equation selecting these two points along this line.

Therefore, we want to represent the linear part of Groebner basis using a linear combination of our equations with polynomial coefficients – $c+ \sum_k a_k x_k +b_k y_k = P_1 h+ \sum_k P_{2,k} f_k + P_{3,k} g_k$ with $P_{...} \in \mathbb{C}[x_1,..., x_n, y_1, ..., y_n]$, Here, the coefficients in the polynomials $P$ are treated as indeterminates. For example, for $n=1$ the correspondin system reads

$\left\{ \begin{array}{lll} f_k= &x_1^2-x_1 & =0 \\ g_k= &y_1^2-y_1 &=0 \\ h_{1,1}= &\left( 1+ 2 x_1 \right) \left( 1+ 2 y_1 \right) -N & = 0 \end{array} \right.$

The linear bases is expressed by

$\begin{array}{l} c+ a_1 x_1 +b_1 y_1 = \\ \left( r_{1,1} x_1 +r_{1,2} y_1 +r_{1,3} \right) (x_1^2-x_1)+ \\ \left( r_{2,1} x_1 +r_{2,2} y_1 +r_{2,3} \right) (y_1^2-y_1)+ \\ \left( r_{3,1} x_1 +r_{3,2} y_1 +r_{3,3} \right) (1+2 x_1+2 y_1+4 x_1 y_1-N) \end{array}$.

and we have the following system for coefficients of different monomials

$\left\{ \begin{array}{rrl} x_1^3: & r_{1,1}&=0 \\ x_1^2y_1: &r_{1,2} +4r_{3,1} &=0 \\ x_1^2:& r_{1,3} - r_{1,1} +2 r_{3,1} &=0\\ x_1y_1^2:& r_{2,1}+4r_{3,2} &=0\\ x_1y_1:& -r_{1,2}-r_{2,1} +2r_{3,1}+2r_{3,2}+4r_{3,3}&=0\\ x_1:& -a_1 -r_{1,3}-r_{3,1}(N-1)+2r_{3,3} &=0\\ y_1^3:& r_{2,2} &=0\\ y_1^2:& r_{2,3}-r_{2,2} +2r_{3,2}&=0\\ y_1:& -b_1 -r_{2,3} -r_{3,2} (N-1) +2r_{3,3} &=0\\ 1:& c+ r_{3,3} (N-1) &=0\\ \end{array} \right.$

$\left\{ \begin{array}{rrl} x_1^2y_1: &-r_{1,2} &=4r_{3,1} \\ x_1y_1^2:& -r_{2,1}&=4r_{3,2} \\ x_1^2:& -r_{1,3} &=2 r_{3,1}\\ y_1^2:& -r_{2,3} &=2r_{3,2}\\ x_1y_1:& 2r_{3,3}&=-3(r_{3,1}+r_{3,2})\\ x_1:& r_{3,1}N+3r_{3,2} &=a_1\\ y_1:& r_{3,2} N+3r_{3,1} &=b_1\\ 1:& -3(r_{3,1}+r_{3,2})(N-1) &=2c\\ \end{array} \right.$

Therefore,
$(N r_{3,1}+3r_{3,2}) x_1+ ( N r_{3,2} +3r_{3,1} ) y_1 - \frac{ 3}{2}(r_{3,1}+r_{3,2})(N-1)= \\ \left( -4r_{3,1} y_1 -2r_{3,1} \right) (x_1^2-x_1)+ \\ \left( -4r_{3,2} x_1 -2r_{3,2} \right) (y_1^2-y_1)+ \\ \left( r_{3,1} x_1 +r_{3,2} y_1 - \frac{ 3}{2}(r_{3,1}+r_{3,2}) \right) (1+2 x_1+2 y_1+4 x_1 y_1-N)$

So the left-hand side of the equation can be written as

$[r_{3,1}, r_{3,2}] \left[ \begin{array}{ccc} N &3 & \frac{ 3}{2}(1-N) \\ 3 &N &\frac{ 3}{2}(1-N) \end{array} \right] \left[ \begin{array}{c} x_1\\y_1\\1 \end{array} \right]$

What we can see here is that the matrix in the above expression has rank 2, unless $N=3$, where the rank of the matrix is 1. When $N=3$ the nullspace of the matrix is

$\left[ \begin{array}{c} 1 \\ 0 \\ 1 \end{array} \right], \left[ \begin{array}{c} -1 \\ 1 \\ 0 \end{array} \right]$

which correspond to two solutions – $x_1= 1, y_1= 0 \rightarrow 3= 3*1$, and $x_1= 0, y_1= 1 \rightarrow 3= 1*3$. Otherwise the null space is expressed as

$\left[ \begin{array}{c} \frac{3(N-1)}{2(N+3)} \\ \frac{3(N-1)}{2(N+3)} \\ 1 \end{array} \right]$

So, for $N=1$ $x_1=y_1= 0 \rightarrow 1= 1*1$, and for $N=9$ $x_1= 1, y_1= 1 \rightarrow 9= 3*3$.

Overall, despite we started with 9+3 indeterminates there are only 2 are relevant to the problem. The question is now how does it scales with $n$. Or another question, is it at all possible to find an algorithm that will select only relevant monomials in $P_{...}$.

Let’s try to extend analysis to the case $n=2$.
To be continued.