Conjuncted: Integer Pivoting as a Polynomial-Time Algorithm


The Lemke-Howson Algorithm follows the edges of a polyhedron, which is implemented algebraically by pivoting as used by the simplex algorithm for solving a linear program. Let us see, if there is an efficient implementation that has no numerical errors by storing integers of arbitrary precision. The constraints defining the polyhedron are thereby represented as linear equations with nonnegative slack variables. For the polytopes P and Q in

P = {x ∈ RM| x ≥ 0, Bx ≤ 1},

Q = {y ∈ RN |Ay ≤ 1, y ≥ 0}

these slack variables are nonnegative vectors s ∈ RN and r ∈ RM so that x ∈ P and y ∈ Q iff

Bx + s = 1, r + Ay = 1 —– (1)


x ≥ 0, s ≥ 0, r ≥ 0, y ≥ 0 —— (2)

A binding inequality corresponds to a zero slack variable. The pair (x, y) is completely labeled iff xiri = 0 ∀ i ∈ M and yjsj = 0 ∀ j ∈ N, which by (2) can be written as the orthogonality condition

xr = 0, ys = 0

A basic solution to (1) is given by n basic (linearly independent) columns of Bx + s = 1 and m basic columns of r + Ay = 1, where the nonbasic variables that correspond to the m respectively n other (nonbasic) columns are set to zero, so that the basic variables are uniquely determined. A basic feasible solution also fulfills (2), and defines a vertex x of P and y of Q. The labels of such a vertex are given by the respective nonbasic columns.

Pivoting is a change of the basis where a nonbasic variable enters and a basic variable leaves the set of basic variables, while preserving feasibility (2).

Integer pivoting always maintains an integer matrix (or “tableau”) of coefficients of a system of linear equations that is equivalent to the original system Bx + s = 1, in the form

CBx + Cs = C1 —– (3)

In (3), C is the inverse of the basis matrix given by the basic columns of the original system, multiplied by the determinant of the basis matrix. The matrix C is given by the (integer) cofactors of the basis matrix; the cofactor of a matrix entry is the determinant of the matrix when the row and column of that element are deleted. When each entry has a bounded number of digits (by at most a factor of n log n compared to the original matrix entries), then integer pivoting is a polynomial-time algorithm. It is also superior to using fractions of integers or rational numbers because their cancelation requires greatest common divisor computations that take the bulk of computation time.

Grothendieck’s Universes and Wiles Proof (Fermat’s Last Theorem). Thought of the Day 77.0


In formulating the general theory of cohomology Grothendieck developed the concept of a universe – a collection of sets large enough to be closed under any operation that arose. Grothendieck proved that the existence of a single universe is equivalent over ZFC to the existence of a strongly inaccessible cardinal. More precisely, 𝑈 is the set 𝑉𝛼 of all sets with rank below 𝛼 for some uncountable strongly inaccessible cardinal.

Colin McLarty summarised the general situation:

Large cardinals as such were neither interesting nor problematic to Grothendieck and this paper shares his view. For him they were merely legitimate means to something else. He wanted to organize explicit calculational arithmetic into a geometric conceptual order. He found ways to do this in cohomology and used them to produce calculations which had eluded a decade of top mathematicians pursuing the Weil conjectures. He thereby produced the basis of most current algebraic geometry and not only the parts bearing on arithmetic. His cohomology rests on universes but weaker foundations also suffice at the loss of some of the desired conceptual order.

The applications of cohomology theory implicitly rely on universes. Most number theorists regard the applications as requiring much less than their ‘on their face’ strength and in particular believe the large cardinal appeals are ‘easily eliminable’. There are in fact two issues. McLarty writes:

Wiles’s proof uses hard arithmetic some of which is on its face one or two orders above PA, and it uses functorial organizing tools some of which are on their face stronger than ZFC.

There are two current programs for verifying in detail the intuition that the formal requirements for Wiles proof of Fermat’s last theorem can be substantially reduced. On the one hand, McLarty’s current work aims to reduce the ‘on their face’ strength of the results in cohomology from large cardinal hypotheses to finite order Peano. On the other hand Macintyre aims to reduce the ‘on their face’ strength of results in hard arithmetic to Peano. These programs may be complementary or a full implementation of Macintyre’s might avoid the first.

McLarty reduces

  1. ‘ all of SGA (Revêtements Étales et Groupe Fondamental)’ to Bounded Zermelo plus a Universe.
  2. “‘the currently existing applications” to Bounded Zermelo itself, thus the con-sistency strength of simple type theory.’ The Grothendieck duality theorem and others like it become theorem schema.

The essential insight of the McLarty’s papers on cohomology is the role of replacement in giving strength to the universe hypothesis. A 𝑍𝐶-universe is defined to be a transitive set U modeling 𝑍𝐶 such that every subset of an element of 𝑈 is itself an element of 𝑈. He remarks that any 𝑉𝛼 for 𝛼 a limit ordinal is provable in 𝑍𝐹𝐶 to be a 𝑍𝐶-universe. McLarty then asserts the essential use of replacement in the original Grothendieck formulation is to prove: For an arbitrary ring 𝑅 every module over 𝑅 embeds in an injective 𝑅-module and thus injective resolutions exist for all 𝑅-modules. But he gives a proof in a system with the proof theoretic strength of finite order arithmetic that every sheaf of modules on any small site has an infinite resolution.

Angus Macintyre dismisses with little comment the worries about the use of ‘large-structure’ tools in Wiles proof. He begins his appendix,

At present, all roads to a proof of Fermat’s Last Theorem pass through some version of a Modularity Theorem (generically MT) about elliptic curves defined over Q . . . A casual look at the literature may suggest that in the formulation of MT (or in some of the arguments proving whatever version of MT is required) there is essential appeal to higher-order quantification, over one of the following.

He then lists such objects as C, modular forms, Galois representations …and summarises that a superficial formulation of MT would be 𝛱1m for some small 𝑚. But he continues,

I hope nevertheless that the present account will convince all except professional sceptics that MT is really 𝛱01.

There then follows a 13 page highly technical sketch of an argument for the proposition that MT can be expressed by a sentence in 𝛱01 along with a less-detailed strategy for proving MT in PA.

Macintyre’s complexity analysis is in traditional proof theoretic terms. But his remark that ‘genus’ is more a useful geometric classification of curves than the syntactic notion of degree suggests that other criteria may be relevant. McLarty’s approach is not really a meta-theorem, but a statement that there was only one essential use of replacement and it can be eliminated. In contrast, Macintyre argues that ‘apparent second order quantification’ can be replaced by first order quantification. But the argument requires deep understanding of the number theory for each replacement in a large number of situations. Again, there is no general theorem that this type of result is provable in PA.

Sobolev Spaces


For any integer n ≥ 0, the Sobolev space Hn(R) is defined to be the set of functions f which are square-integrable together with all their derivatives of order up to n:

f ∈ Hn(R) ⇐⇒ ∫-∞ [f2 + ∑k=1n (dkf/dxk)2 dx ≤ ∞

This is a linear space, and in fact a Hilbert space with norm given by:

∥f∥Hn = ∫-∞ [f2 + ∑k=1n (dkf/dxk)2) dx]1/2

It is a standard fact that this norm of f can be expressed in terms of the Fourier transform fˆ (appropriately normalized) of f by:

∥f∥2Hn = ∫-∞ [(1 + y2)n |fˆ(y)|2 dy

The advantage of that new definition is that it can be extended to non-integral and non-positive values. For any real number s, not necessarily an integer nor positive, we define the Sobolev space Hs(R) to be the Hilbert space of functions associated with the following norm:

∥f∥2Hs = ∫-∞ [(1 + y2)s |fˆ(y)|2 dy —– (1)

Clearly, H0(R) = L2(R) and Hs(R) ⊂ Hs′(R) for s ≥ s′ and in particular Hs(R) ⊂ L2(R) ⊂ H−s(R), for s ≥ 0. Hs(R) is, for general s ∈ R, a space of (tempered) distributions. For example δ(k), the k-th derivative of a delta Dirac distribution, is in H−k−1/2</sup−ε(R) for ε > 0.

In the case when s > 1/2, there are two classical results.

Continuity of Multiplicity:

If s > 1/2, if f and g belong to Hs(R), then fg belongs to Hs(R), and the map (f,g) → fg from Hs × Hs to Hs is continuous.

Denote by Cbn(R) the space of n times continuously differentiable real-valued functions which are bounded together with all their n first derivatives. Let Cnb0(R) be the closed subspace of Cbn(R) of functions which converges to 0 at ±∞ together with all their n first derivatives. These are Banach spaces for the norm:

∥f∥Cbn = max0≤k≤n supx |f(k)(x)| = max0≤k≤n ∥f(k)∥ C0b

Sobolev embedding:

If s > n + 1/2 and if f ∈ Hs(R), then there is a function g in Cnb0(R) which is equal to f almost everywhere. In addition, there is a constant cs, depending only on s, such that:

∥g∥Cbn ≤ c∥f∥Hs

From now on we shall always take the continuous representative of any function in Hs(R). As a consequence of the Sobolev embedding theorem, if s > 1/2, then any function f in Hs(R) is continuous and bounded on the real line and converges to zero at ±∞, so that its value is defined everywhere.

We define, for s ∈ R, a continuous bilinear form on H−s(R) × Hs(R) by:

〈f, g〉= ∫-∞ (fˆ(y))’ gˆ(y)dy —– (2)

where z’ is the complex conjugate of z. Schwarz inequality and (1) give that

|< f , g >| ≤ ∥f∥H−s∥g∥Hs —– (3)

which indeed shows that the bilinear form in (2) is continuous. We note that formally the bilinear form (2) can be written as

〈f, g〉= ∫-∞ f(x) g(x) dx

where, if s ≥ 0, f is in a space of distributions H−s(R) and g is in a space of “test functions” Hs(R).

Any continuous linear form g → u(g) on Hs(R) is, due to (1), of the form u(g) = 〈f, g〉 for some f ∈ H−s(R), with ∥f∥H−s = ∥u∥(Hs)′, so that henceforth we can identify the dual (Hs(R))′ of Hs(R) with H−s(R). In particular, if s > 1/2 then Hs(R) ⊂ C0b0 (R), so H−s(R) contains all bounded Radon measures.