Semiprime factorization and modular arithmetics

Edit 6.6.2016. Premature optimization is a source for errors. The following is completely wrong. Would like to smoke the same thing again. Linear algebra does not work here. We need characterization of quotient space. What I do not understand is why fast methods are working modulo number itself, but not other prime numbers.

---

Suppose we have number , where we know and want to find prime factors and .

Lets take small prime , than we can write .

Step 0

One can observe that , since multiplication group modulo prime is cyclic for each there is unique satisfying the equation. In other words we need to test values to find correct one, if we can. From now on I assume satisfy and therefore divides .

Step 1

One can observe that , so we can write since . In other words . Substituting it into original equation we get . Summarizing,

.

Step 2
.

…

Step
where is a univariate polynomial on of degree

Final Step
In other words Substituting this into original equation we will get modular univariate polynomial equation of degree . We need to factorize it and check values of resulted .

I’ll leave the analysis of algorithm complexity to professionals. Have fun.

Why P could be equal NP

In the previous post we have established relation between P vs NP problem and quartic positive polynomial optimization problem. Here I will give some intuition why it is possible that we would be able to decide that quartic polynomial has non-zero global minimum. I’ll give only the short intuition leaving details for professionals. I’m not interested in putting all comas in place.

Ingredients:

1. NP-complete decision problems
2. Non-negative quartic polynomials
3. Reznick perturbation lemma
4. Sum of squares optimization
5. Blekherman beautiful high school exposition about why not all positive quartics are sums of squares
6. Extremal polynomials
7. Some combinatorics
8. Semialgebraic geometry

---

1. NP-complete problems:
   Partition problem: Given a multiset of integers is it possible to divide it into complementary multisets having the same sum, i.e. whether there exist such that .
   For those who loves 3-SAT: given a set of logical clauses having exactly 3 binary variables (literals) each, decide whether all clauses can be satisfied (evaluated true) at once. To encode it, we want the set of polynomial equation evaluating 0 when clause is true: would be translated into .
2. Quartics:
   ,
   ,
   Combining together we have for partition problem: ; for 3-SAT: , where is one 3 term clause. The last equation is not always positive, but for large enough it is, when problem is not satisfiable, thanks to third ingredient.
3. Reznick perturbation lemma (3.1 in the reference) adapted to quartics:
   Given positive polynomial with no zeros at infinity (), condition 1 in the Lemma. If NP-complete problem is not satisfiable , condition 2. Finally,  , where are zero set of , a set of where polynomial vanishes. Therefore, there exists that is positive.
   It should be noted here that global minimum is polynomially bounded away from 0, and constant c too.
5. Both are covered in the previous post. In short the number of coefficients in quadratic polynomials (squared they give quartic sum of squares) is roughly quadratic. It is sufficient to fix the value of quadratic polynomial at quadratic number of points to constrain all coefficients, and therefore to constrain the values at all points in a hypercube of interest. The number of coefficients in quartic polynomial is roughly quartic, therefore there is more freedom in choice of coefficients. It is possible to select quartic coefficient in a way that will constrain all values of quadratic to 0 on hypercube.
6. The simple example of quartic polynomial that is not sum of squares is Robinson polynomial: . This is extremal polynomial (Choi, Lam (1977), Reznick (2007) )  – it cannot be non-trivially decomposed into other forms. This polynomial has seven zeros on the hypercube and one non zero value. Therefore, we can independently control value at one vertex of hypercube (1,1,1) by multiplying Robinson polynomial by positive constant.
7.  Let , i.e. we replace , we say negation (by analogy with binary variables and there translation to polynomials). This is also extremal positive polynimial that controls value at (0,1,1). Same way we can make all extremal polynomials that controls independently all vertices of a hypercube. Let be a linear combination of all Robinson polynomials controlling different vertices of hypercube in 3 variables with positive coefficients (i.e. a point inside the cone of positive polynomials defined by the Robinson polynomials).Now consider polynomial . Once the value of this polynomial at is positive, there exists such that this polynomial is positive! The same is true if we sum up all negations of quartic:  . Once values on 16 hypercube vertices are positive there is that for all the polynomial is positive.  Note that all 16 vertices are controlled independently.

   Now take all the combinations of 4 coordinates/variables/literals out of n dimensions/variables/literals of the problem. Construct the polynomials from the previous paragraph for all combinations and take linear combination of them with positive coefficients. We get positive polynomials (not extreme) that have control over quartic number of points (in the number of variables) which is exactly the number of points required to constraint all coefficients of quartic polynomial. It should be noted that we would not be able to find the global minimum of the polynomial because of the requirement that quartic terms (that are not controlled by the Robinson terms) should be evaluated at positive values, but remember that there is polynomial gap for unsatisfiable problem. Therefore, we can require all vertices to have positive values.

   The only missing part here is the estimation on the bound for value. This may be large, but should be polynomial in the number of bits and number of dimensions.

8. We actually interested in the positive solution inside hypercube. So, we have additional terms to reduce the complexity of the problem, i.e. semialgebraic bound on the region: for 3-SAT and for partition problem. It adds additional freedom in the choice of variables, and limits the value of being quite small.

Finally we can control values of quartic polynomial in quartic number of points such that differences between given unsatisfiable problem and resulting quartic be sum of squares, including 1. In the later case we have linear program in polynomial number of variables.

I’m not a mathematician, and hate all comas in place. I’m more than happy to unpack unclear points, but will refuse to estimate so no one would claim I solved the problem, in case. And remember, the science is moving forward not because established scientists change their mind, but because young people come.

Sincerely yours,

C.T.

---

Update 12 Jan 2016.

I see where the skepticism comes from. The perturbation can be quite strong. We can require quartic polynomial being zero (with zero grdient) at roughly cubic number of generic points. all quadratics would be zero in this space since they have only quadratic number of monomials, so we have over-determined system of linear equations on the coefficients of quadratics. On the other hand we can freely move those cubic points in space (up to infinity) and still get possibly positive polynomials. This is the problem on one hand, on the other hand, this opens a way for continuation methods. By the way by the homogenization the problem of infinity is replaced by the path along unit sphere. Therefore, there is more good than bad. I imagine a continuation method for solving optimization problem by starting with well defined positive polynomials (say sums of squares) and splitting extra solutions from well defined ones(say on a hypecube) toward correct coefficients until we get enough of them (up to a cubic, where by the number of coefficient they will approach extremal polynomials). We can actually have a polynomial number of separate splits with their (conical/non-negative) sum leading to desired optimized polynomial. The big question here is preservation of positivity, which is a global property.

---

update 24 jan 2016

Rhe following is in words that needs translation to math.

If we start with sums of squares which have clear solution, we can now peak a cubic point around solution (very close) and require the qurtic polynomial to be round at this points (i.e. the value and gradient are zero at these points and Hessian is positive definite ) than this polinomial will be positive and is not sum of squares. More generaly, the quartic polynomial will positive if more than square points (number of monomials in quadratic polinomial of the same dimension) are round and there is continuous path to original sum of squares such that this property holds for every point in the path. That would an alternative ( to Hilbert method) way to construct positive polynomials.

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 , where and are some polynomials it is obvious that 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 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 , where is an arbitrary unique symbol denoting variable. For example, . Let being evaluation of the set at point . For example, for any point x, . , where . Let polynomial be a linear combination of elements of , where enumerates elements of the set.

NP-complete integer partition problem

Let . Integer partition problem is asking whether , 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 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 . The second sum at given values can be zero only when partition exists

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

Zeros of quadratics on hyper-cube
Here we would like to establish some properties of the quadratic polynomials on the hyper-cube

Propostiion 2 Consider quadratic polynomial . If than .

Proof

Consequitively,
.
.
, taking into account second case.

Finally, , which is clearly 0 for , since in each term in the sum either first or second factor is 0

Quartics that vanish on
.

Consequently,
.
.
, taking into account second case.

Additionally, we want quartics to preserve sign around , since we are interested in positive polynomials. Necessary condition is that gradient equals 0 for corresponding points.

.

Consequently,
.
is splitted into 2 cases. and
together with that lead to
.
split again into the same cases.
together with and that lead to .
. The last condition counted over triplet lead to Robinson perturbation term

Combining all conditions together we get

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

---

Update Jan 6 2016

What is interesting is that
(1) if quartic is positive and has zeros forming n-simplex than its form is constrained. After a linear transformation this simplex can be transformed into standard orthogonal simplex with zeros being at
(0,0,0,…, 0),
(1,0,0,…, 0),
(0,1,0,…, 0),
(0,0,0,…, 1).
This leads to constraints on the coefficients of positive quartic polynomials. For instance, zero at 0 lead to . Zero gradient (necessary for quartic being positive) leads to . Zeros at other vertices lead to the following constraint , whereas zero gradient leads to leading to null-space , i.e. for any which leads to polynomial
, where have no single variable term. Therefore, this simple requirement leads to representation of quartic positive polynomial as sums of squares plus some perturbation.

(2) It is sufficient to spread enough zeros across space, not necessary on the corner of hyper-cube to nullify all coefficient of quadratics. There are coefficients in quadratics. For the corresponding quartic we need at least generic points where quartic and its gradient vanish. That leads to constraints. We need more coefficients to have some freedom. That is achievable for the dimension more than 5. That is saying that perturbation can be very strong.

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 points in n-dimensional hypercube, but since there are only 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 is . 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 (), splitting points in the hypercube into two sets. In one set we require that Taylor expansion of vanish to second order term, and on the other set we require that is strictly positive. Only those points in the hypercube are dangerous, since perturbation may lead to negative values around minima for any positive . In the rest of the space we can choose small enough to ensure positiveness of resulting polynomial (I skip this part, but one need to have worst estimate for the values of for a given norm of and take a region bounded by some norm and outer region where only ratios between leading coefficients matter). For the first set of points 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 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 conditions for about 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 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:

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))]


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 with entries tell whether it is possible to divide it into two miltisets having the same sum. Formally, tell whether there exists vector such that , or in vector notation . This problem is NP-complete.

2. It is possible to encode this problem into minimization of quartic polinomial:

The minimum is zero when exists and is greater than zero otherwise. Moreover, non-zero value is inversely bounded by length of the vector .

3. Non-zero minimum exists if , where is positive semidefinite polynomial ( a polynomial that is non-negative over whole range of values ), 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 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 runners having distinct constant speeds 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 from the origin.

W.l.o.g. we can assume .

One can formulate LRC as follows. Suppose is the number of whole laps (including 0) runner k passed on a track, than and .

Case n=1, two runners is trivial. At time runner 1 is exactly distance ().

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

We start with 4 inequalities

Since 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.

The first and the last inequality are trivially correct. From the second and third inequality we would like to express

In other words,

There are 2 sub-cases.

1. Sub-case
   and satisfying inequality
2. Sub-case
   In this case lead to (remeber that )
   

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

We start with 6 inequalities

Let’s express in terms of

Rewriting it we obtain

since In other words, satisfying inequality.

Now, let express in terms of and

We can express with inequalities obtained earlier

Collecting terms we obtain

We can see that first inequality is always stronger that the second one (meaning that if satisfies first inequalities it will satisfy second inequalities). But the first inequalities are the same as previous inequalities for with relabelling. Therefore, satisfying initial inequalities and LRC holds.

General case

We start with inequalities

Now we expressing in terms of and in terms of and

Now we can substitute first inequalities into the second ones.

Rearranging terms we obtain

Compare it to

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!!! )

Lets rewrite it again

if

---

It is not clear from this why is tight distance.

---

11.2.2016
It is clear why it is not clear. The above just tell that with speed ratio more the one we can always find a lap for faster runner. The tightness comes from from ratios less than one. Most probably from the interactions or the ratios coming from the same pairs.

On the lonely runner conjecture III

We consider (LRC) .

Conjecture Suppose runners having distinct constant integer speeds 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 from the origin.

Case of runners is discussed here. Here we look at case .

Let denote the distance of x to the nearest integer.

Case . At time all runners are at least from the origin. Done.

Case . There is time such that runners are at least from the origin – see case . At time runners are at the same positions as runners at time . If at time , we are done. Otherwise, since and 5 are co-prime, . Done.

Case .

Definition Sector .
There is a time such that runners are at least from the origin – see case . Since and 5 are co-prime those runners visit all sectors once at times , and runners 1 and 2 will be at the same position. There 5 such times, during 2 times runner 3 will be at sectors and during 2 times runner 4 will visit the same sectors. Therefore, there is . Done.

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

Case .

Rearrange speeds that . If there more than one way choose the one with maximum sum. We have 2 sub-cases: , .

1. 
   . The runner 1 is faster than either runner 2 or 3. Therefore, they meet at distance greater than .

   Now runner 4.

   1. this runner is slower than either runner 2 or 3 (call this runner ) which is at the same position as runner 4. Therefore, it will meet runner 1 later than runner , which meet runner 1 at distance larger than . Done.
   2. . This runner should move fast to reach runner 1 at distance . So, it will cover at least 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 from the origin when runner 1 reach distance If it is moving even faster to meet runner 1 at 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 . Done.
2. This is the most interesting case.

   At times runners 2 and 3 are the same distance from the origin on the opposite sides from the origin.

   Runner 1 exhibit repeated motion at . It makes cycles, where stands for greatest common divisor. The number of different positions it attain evenly distributed along the track is . If half of the time runner 1 is away from the origin. With larger there is bigger fraction, with the limit . Let 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 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 , and there are total, possibly different 2 times runner 2 in , on the other hand when runner 2 in sector 0 runner 3 is in sector 4 and vice verse. Therefore, there is . Done.

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 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 and bring new ingredients (non prime , and competition between 2 pairs of paired runners ). May be we need to wait for the new ingredient until .

On the lonely runner conjecture II

We consider (LRC) .

Conjecture Suppose runners having distinct constant integer speeds 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 from the origin.

We first show trivial proves for runners.

Let denote the distance of x to the nearest integer.

Let . where the infimum is taken over all n-tuples of distinct positive integers.

In terms of the LRC state that

Without loss of generality (wlog) we can assume .

Case . Wlog we can assume are relatively prime. At time two runners are at the same distance from the origin from different sides of the lap at distances proportional to . Since they are relatively prime both runners visit all the points . The largest distance is , where means integer part.

For example, , at times runners are at positions and and the maximum distance from origin is .

Another example, , the maximum distance is .

If the maximum distance is at time .

In general the maximum distance is with the minimum for runners at speeds . Therefore, .

Case .

• First we assume simple case: , e.g .

  At times 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 ). 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 with speed , so the time needed is . Runner 3 passes . Therefore, the closest point is reached when is maximum.

  

  If , around

  

  Lemma 1. .
  Proof.

  Now, consider the case when .

  

  Lemma 2.
  Proof. . Since nominator is greater than 0, except when

  Corollary 3. .
  Corollary 4. only for .

• Case: .

  Lemma 5. Fix time . Let be the distance from the origin of runner 3 at the moment and 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 is greater than .
  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 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 runner 3 will cover greater distance away from the origin that other runner

  Lemma 6. Fix the time when . Let , and – distance of runner 3 from the origin. .
  Proof. ,

  Combining Lemma 5 and Lemma 6 shows .

Overall, only for runners .

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 , where index enumerates rows, and index enumerates columns. Each element is independent binary random variable with equally probable possible states and . Suppose is a realization of random variables. We are going to fix it for the rest of the post.

Cantor diagonal argument Let row . Since, 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 in the table with probability 1.
Proof 1. Select the subset of rows () where the first column has value : . Since is a realization of independent random variable, there are infinite number of rows in with probability one. Moreover, viewing as a table one can see that , and is a realization of equi-probable binary random variable.

Induction step. Suppose there is a set of countable many rows such that . We select from the table a subset of rows that have . The set consists of countable infinite number of rows with probability 1. Moreover, the table divided into 2 parts. The left part- columns from 1 to – all rows coincide with . The right part – all columns starting from are realization of independent random variable.

Therefore, by induction, there is set “ that is countably infinite with probability 1, and each member consists of rows . QED.

If one interpret table as membership table, e.g. a set 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 are ordered by the rows and particular implementation of random variables.

Applying weights to the column, e.g. representing real numbers shows there are countable many reals, and moreover there are countable many equal reals.

Nullspace of tautologies

Below is Mathematica printout showing the usefulness of tautologies.
tautologies6vars4thOrder

Given and equations , 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 . 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.