diff c022cea..a30d6a9 crossing_number_bipartite_v2.txt
diff --git a/crossing_number_bipartite_v2.txt b/crossing_number_bipartite_v2.txt
index fb27ba6..1e797f3 100644
--- a/crossing_number_bipartite_v2.txt
+++ b/crossing_number_bipartite_v2.txt
@@ -1,1770 +1,1158 @@
THE CROSSING NUMBER OF COMPLETE BIPARTITE GRAPHS
-A self-contained proof of the Zarankiewicz conjecture
-Written for curious high school students. Every step is explained.
+A complete proof of the Zarankiewicz conjecture, written for curious high
+school students.
==============================================================================
-TABLE OF CONTENTS
+CONTENTS
==============================================================================
- Part I What we are proving
- 1. The short version
- 2. Graphs, drawings, and crossings
- 3. The formula and small examples
- 4. The easy half: a good drawing (upper bound)
-
- Part II The plan for the hard half
- 5. Why lower bounds are hard
- 6. The three ingredients
-
- Part III The algebraic tools
- 7. A linear algebra crash course
- 8. The subspace intersection lemma
- 9. Ranks of matrix differences
-
- Part IV The geometric machinery
- 10. Signed intersections of oriented edges
- 11. The chord formula
- 12. The cycle pairing lemma
- 13. The additive block relation
-
- Part V The detector
- 14. Lagrange interpolation
- 15. The two-triangle interpolation lemma
- 16. Building and verifying the rank detector
-
- Part VI The finish
- 17. Assembling the lower bound
- 18. The odd case
- 19. The even case
- 20. Cleaning up a drawing (appendix)
- 21. Where to learn more
+ Part I Setting the scene Sections 1-3
+ Part II The upper bound Section 4
+ Part III The lower bound plan Section 5
+ Part IV Algebraic tools Sections 6-8
+ Part V Geometric machinery Sections 9-12
+ Part VI The rank detector Sections 13-15
+ Part VII The odd case Section 16
+ Part VIII The even case Section 17
+ Part IX Normalizing a drawing Section 18
+ Part X Further reading Section 19
==============================================================================
-PART I WHAT WE ARE PROVING
+HOW TO READ THIS DOCUMENT
==============================================================================
-1. THE SHORT VERSION
-------------------------------------------------------------------------------
+ The argument is long but each piece is simple. Suggested reading order
+ for a high school student:
-Draw m dots down one column and n dots down another. Connect every dot on
-the left to every dot on the right. Lines will cross each other as they
-wind around. The question is: what is the fewest possible number of
-crossings, over all ways of drawing?
+ First pass (the whole idea in a page):
+ Sections 1-5. Learn the problem, the easy upper bound, and the
+ plan for the hard lower bound. Do NOT get bogged down.
-Answer. Let
+ Second pass (the tools):
+ Sections 6-8 (linear algebra). These are self-contained; no
+ background is required. Then Sections 9-12 (geometry). The
+ proofs here are wordy but picture-driven.
- d_r = floor(r/2) * floor((r-1)/2)
+ Third pass (the crown jewel):
+ Sections 13-15 (the "rank detector"). This is where Lagrange
+ interpolation meets two-triangle combinatorics. Read the easier
+ case s=1 first (n=3), then s=2 (n=5), then general s.
-where floor(x) is x rounded down. Then, for every pair of positive
-integers m, n,
+ Final pass (assembly):
+ Sections 16-17. The three tools click together into the theorem.
- cr(K_{m,n}) = d_m * d_n.
+ Sections 18-19 (normalization and references) can be skimmed on first
+ reading; they back up technical claims that a first-time reader may
+ reasonably take on faith.
-Examples. The d-values are:
-
- r: 1 2 3 4 5 6 7 8 9 10 11 12
- d_r: 0 0 1 2 4 6 9 12 16 20 25 30
-
-So cr(K_3,3) = 1 * 1 = 1. cr(K_4,5) = 2 * 4 = 8. cr(K_7,7) = 9 * 9 = 81.
-
-That is the whole result. The rest of this document explains what it
-means, gives more examples, and proves it completely. The proof is long
-but every ingredient is simple; nothing requires advanced mathematics
-beyond what a curious high school student has seen.
-
-Why does this matter? Two reasons.
-
-(a) It was open. Zarankiewicz proposed this formula in 1955. Nobody could
- prove it for seventy years. It is one of the most famous unsolved
- problems in combinatorial geometry.
-
-(b) The proof is beautiful. It combines signed intersections of curves,
- a "rank detector" built from Lagrange interpolation, and a "subspace
- intersection" inequality. High schoolers can follow all of it.
-
-2. GRAPHS, DRAWINGS, AND CROSSINGS
-------------------------------------------------------------------------------
-
-2.1 Graphs. A graph consists of vertices (dots) and edges (lines joining
-pairs of dots). We assume no loops (a vertex joined to itself) and no
-multiple edges between the same pair.
-
-2.2 Complete bipartite graphs. Fix integers m, n >= 1. The complete
-bipartite graph K_{m,n} has two groups of vertices:
-
- A = {a_1, ..., a_m} (the "left side")
- B = {b_1, ..., b_n} (the "right side")
-
-Every a_i is connected to every b_j (1 <= i <= m, 1 <= j <= n). No two
-vertices inside A are connected to each other; same for B. Total number
-of edges: m*n.
-
-Picture the m dots of A as kilns and the n dots of B as storage yards.
-Every kiln is linked to every yard by a rail line. That is m*n rail
-lines. We want to arrange the kilns, yards, and rail lines so lines
-cross as little as possible.
-
-2.3 Drawings. To draw a graph, place its vertices at distinct points in
-the plane and draw each edge as a continuous curve (an arc) between its
-endpoints. The arc's interior must not touch any other vertex.
-
-A drawing is ADMISSIBLE if it satisfies four "no degeneracy" rules:
-
- (a) Only finitely many pairs of edges meet in their interiors.
- (b) Every such meeting is a PROPER CROSSING: the two edges pass
- through each other, like the strokes of an X.
- (c) No three edges meet at one common interior point.
- (d) Edges never touch tangentially and never share a whole arc.
-
-Rules (c) and (d) just say "no silly coincidences". You can always jiggle
-a bad drawing a tiny amount to fix them.
-
-2.4 Crossings and the crossing number. In an admissible drawing D, a
-CROSSING is a proper meeting of two edge interiors. Let c(D) be the
-number of crossing POINTS. If the same two edges cross twice, that is
-two crossings (two distinct points). The crossing number of a graph G
-is
-
- cr(G) = min over all admissible drawings D of c(D).
-
-This minimum exists because any drawing has a nonnegative integer count,
-and the natural numbers are well-ordered.
-
-2.5 Planar graphs. If cr(G) = 0, G is PLANAR: it can be drawn without
-crossings. K_1,n and K_2,n are planar (Section 3). But K_3,3 is NOT
-planar - this is the famous "three houses, three utilities" puzzle.
-So cr(K_3,3) >= 1. Since an explicit one-crossing drawing exists,
-cr(K_3,3) = 1. That is our first small case.
-
-3. THE FORMULA AND SMALL EXAMPLES
-------------------------------------------------------------------------------
-
-3.1 The Zarankiewicz sequence. Define
-
- d_r = floor(r/2) * floor((r-1)/2).
-
-Equivalently,
-
- r even, r = 2s: d_r = s(s-1)
- r odd, r = 2s+1: d_r = s^2
-
-A third form uses binomial coefficients. Recall C(n,2) = n(n-1)/2, the
-number of pairs of distinct objects chosen from n. Then
-
- d_r = C(floor(r/2), 2) + C(ceil(r/2), 2)
-
-where ceil is "round up". Quick check: r = 5. floor(5/2) = 2, ceil(5/2)
-= 3, so C(2,2) + C(3,2) = 1 + 3 = 4, matching d_5 = 2*2 = 4.
-
-Table of values:
-
- r: 1 2 3 4 5 6 7 8 9 10
- d_r: 0 0 1 2 4 6 9 12 16 20
-
-3.2 Theorem (Zarankiewicz 1955; proved here). For all m, n >= 1,
-
- cr(K_{m,n}) = d_m * d_n.
-
-3.3 Backstory. Turan, working at a Budapest brick factory around 1944,
-asked how to arrange kilns and storage yards so that their rail lines
-have the fewest crossings. Zarankiewicz (1955) gave the balanced-column
-drawing and claimed the formula. However, he never proved that no
-smarter drawing could beat it. That missing proof is the hard part, and
-it resisted every attack for decades.
-
-3.4 Small cases, listed and (where possible) verified by hand.
-
- cr(K_1,n) = 0.
- K_1,n is a "star": one dot connected to n others. Stars are
- planar. Formula: d_1 * d_n = 0 * d_n = 0. Match.
-
- cr(K_2,n) = 0.
- Put a_1, a_2 one above the other; put b_1,...,b_n in a column
- to the right. All edges fan out visibly with no crossings (the
- "double fan" is planar). Formula matches because d_2 = 0.
-
- cr(K_3,3) = 1.
- Two-utilities puzzle. Formula: d_3 * d_3 = 1*1 = 1.
-
- cr(K_3,n) = d_3 * d_n = d_n.
- For any n. So cr(K_3,4) = 2, cr(K_3,5) = 4, and so on.
-
- cr(K_4,4) = 4.
- Formula: d_4 * d_4 = 2*2 = 4. Verified by Kleitman (1970).
-
- cr(K_4,5) = 8.
- Formula: 2 * 4 = 8.
-
- cr(K_5,5) = 16. cr(K_6,6) = 36. cr(K_7,7) = 81.
- The K_7,7 case was verified by a computer search by Woodall in
- 1993. Kleitman proved cr(K_{m,n}) = d_m * d_n for all m <= 6.
-
-The formula passes every check we can do. The general case is what the
-rest of this document proves.
-
-3.5 Where the real difficulty lies. Even PROVING cr(K_{n,n}) >=
-(0.9118 + o(1)) * d_n^2 (still slightly below the formula) was a major
-2023 breakthrough by Balogh, Lidicky, Norin, Pfender, Salazar, and
-Spiro, using a heavy technique called flag algebra. So getting from
-"slightly below" to "exactly equal" requires a fundamentally different
-approach - not just better computation.
-
-4. THE EASY HALF: A GOOD DRAWING (UPPER BOUND)
-------------------------------------------------------------------------------
-
-4.1 Goal. Build a drawing of K_{m,n} with exactly d_m * d_n crossings.
-This shows cr(K_{m,n}) <= d_m * d_n.
-
-4.2 Construction (balanced axis). Let
-
- u = floor(m/2), u' = m - u = ceil(m/2)
- v = floor(n/2), v' = n - v = ceil(n/2).
-
- 1. Split the m A-vertices into u at y>0 and u' at y<0.
- 2. Split the n B-vertices into v at x>0 and v' at x<0.
- 3. Place the A-vertices on the y-axis (u above origin, u' below),
- and the B-vertices on the x-axis (v right, v' left). All positions
- distinct, none at the origin.
- 4. Draw every edge a_i -- b_j as a STRAIGHT LINE SEGMENT between its
- two axis positions.
-
-4.3 Why it works: NE quadrant. Every edge sits in exactly one of the
-four open quadrants (or on an axis if its two positions share a sign).
-Look at the first quadrant (NE: x>0, y>0). An edge lands here iff its
-A-endpoint is in the "upper" group and its B-endpoint is in the "right"
-group. Look at two such edges: a_1 -- b_1 and a_2 -- b_2 with a_1, a_2
-distinct upper A-vertices and b_1, b_2 distinct right B-vertices.
-
-The four points a_1, a_2, b_1, b_2 form a convex quadrilateral (a
-rectangle, actually). Of the four segment pairs between them, two are
-"diagonals" (long) and two are "sides" (short). The diagonals cross
-exactly once inside the rectangle; the sides do not cross. Hence every
-distinct pair-of-edges {a_1 b_1, a_2 b_2} of this shape contributes
-EXACTLY one crossing in the NE quadrant.
-
-Number of pairs of upper A-vertices is C(u, 2). Number of pairs of
-right B-vertices is C(v, 2). Hence NE-quadrant crossings = C(u,2)*C(v,2).
-
-4.4 All four quadrants. Similarly:
-
- NE: C(u, 2) * C(v, 2)
- NW: C(u, 2) * C(v',2)
- SE: C(u',2) * C(v, 2)
- SW: C(u',2) * C(v',2)
-
-The total count is
-
- (C(u,2) + C(u',2)) * (C(v,2) + C(v',2)) = d_m * d_n,
-
-where the last equality is exactly the binomial form from Section 3.1
-(since u = floor(m/2), u' = ceil(m/2), and same for v, v').
-
-4.5 Why the split is balanced. With u + u' = m fixed, minimize
-C(u,2) + C(u',2). The function f(u) = u(u-1)/2 + (m-u)(m-u-1)/2 is a
-convex parabola with its minimum at u = m/2. So the best split takes u
-as close to m/2 as possible: u = floor(m/2), u' = ceil(m/2). Same for v.
-
-4.6 Avoiding triple crossings. One subtlety. Suppose three straight
-segments happened to meet at one single point. That point would count
-as ONE crossing point, but it would be "shared" between multiple edge
-pairs. Our count above assumed every pair gives its own distinct
-crossing. To make the count honest, jiggle the axis positions by tiny
-generic amounts. The set of positions where any three segments happen
-to concur is a finite union of polynomial conditions, so most positions
-are fine. A small perturbation keeps all positions distinct and removes
-all triple events without introducing new ones.
-
-4.7 Conclusion. We have constructed a drawing with d_m * d_n crossing
-points. Therefore cr(K_{m,n}) <= d_m * d_n.
-
-That is the easy half. The rest of this document proves the opposite
-inequality:
-
- cr(K_{m,n}) >= d_m * d_n for every m, n.
+ Key checkpoints to test understanding:
+ Section 3: do you see why cr(K_3,3) = 1?
+ Section 4: do you believe cr <= d_m d_n?
+ Section 5: can you state the three ingredients in your own words?
+ Section 8: can you plug in m=2,3,4 and verify the numbers?
+ Section 16.6: can you see where each inequality goes?
==============================================================================
-PART II THE PLAN FOR THE HARD HALF
+PART I SETTING THE SCENE
==============================================================================
-5. WHY LOWER BOUNDS ARE HARD
-------------------------------------------------------------------------------
-
-5.1 Easy vs hard direction. The upper bound cr(K_{m,n}) <= d_m * d_n
-was easy: we just built one specific good drawing. The lower bound
-
- cr(K_{m,n}) >= d_m * d_n
-
-is much harder because it says: NO drawing, no matter how clever, with
-edges bent however wildly, can ever do better. You cannot prove that by
-drawing pictures; you must rule out infinitely many possibilities.
-
-5.2 Analogy. A lower bound on crossings is like a "shut-the-box" puzzle:
-no matter what inputs you feed the drawing, its output must obey some
-inequality. Our strategy is to convert ANY drawing into an algebraic
-expression (a sum of matrix ranks) that is forced to be large. The
-geometry becomes algebra, and a linear-algebra inequality finishes.
-
-5.3 The strategy in one sentence. We convert a minimal drawing into a
-family of matrices R_ik whose ranks are bounded above by the number of
-crossings between the i-th and k-th stars, and a linear-algebra fact
-forces the sum of those ranks to be at least 2 d_m d_n. Therefore at
-least d_m d_n crossings are needed.
-
-6. THE THREE INGREDIENTS
-------------------------------------------------------------------------------
-
-6.1 Overview. Three big pieces, each interesting on its own.
-
- (A) GEOMETRIC RELATIONS. From a drawing, form a matrix J whose entries
- count "signed crossings" between pairs of edges, plus a small
- correction at shared vertices. Closed curves force a special
- shape: J^{ik} - J^{i1} - J^{1k} + J^{11} is always ROW-PLUS-COLUMN
- (Section 13).
-
- (B) A RANK DETECTOR. Construct a linear map Phi from n-by-n matrices
- to d-by-d matrices that "sees" enough structure to turn the
- relations above into a family of matrix differences X_i - Y_j
- with X_i - Y_i invertible and off-diagonal ranks bounded by
- crossings (Sections 16-17).
-
- (C) A RANK-SUM INEQUALITY. Prove that if X_i - Y_i are invertible,
- then sum over i != j of rank(X_i - Y_j) is at least 2 d_m d_n
- (Sections 8-9).
-
-6.2 The three pieces click together as
-
- crossing count <= (rank sum off-diagonal)/2
- >= d_m d_n.
-
-The middle inequality is the geometric estimate on ranks of the block
-matrices; the right-hand side is the rank-sum inequality.
-
-6.3 Why odd n first. If n = 2s+1 is odd, we can label the s^2 "useful"
-pairs (p,q) in a special two-triangle shape that makes the detector
-work. The even case then reduces to the odd case by a vertex-deletion
-trick (Section 19). So the bulk of the work is the odd case.
+1. THE PROBLEM
+
+1.1 Graphs. A GRAPH has VERTICES (points) and EDGES (curves joining
+pairs of vertices). We assume no loops (a vertex joined to itself) and
+no multiple edges between the same pair of vertices.
+
+1.2 Complete bipartite graphs. K_{m,n} has two vertex classes,
+ A = {a_1, ..., a_m} (first class, or "kilns"),
+ B = {b_1, ..., b_n} (second class, or "yards"),
+with an edge a_i b_j for every (i,j) and no other edges. Total edges: mn.
+
+Picture: m kilns at one place, n yards at another, every kiln linked to
+every yard by a railway.
+
+1.3 Drawings and crossings. A DRAWING places the vertices at distinct
+points of the plane and represents each edge by a simple arc whose
+interior avoids all other vertices. A PROPER CROSSING is a point where
+the interiors of two edges meet transversally (like the strokes of an X,
+not a tangency). A drawing is ADMISSIBLE if:
+ (a) it has finitely many crossings;
+ (b) all crossings are proper;
+ (c) no three edges cross at one interior point;
+ (d) no tangencies and no shared arcs.
+A nonadmissible drawing can always be nudged into an admissible one
+without increasing the crossing count.
+
+The CROSSING NUMBER of G is
+ cr(G) = min over admissible D of c(D),
+where c(D) counts crossing POINTS (if a pair of edges crosses twice,
+that is two crossings).
+
+1.4 The formula. Define the Zarankiewicz number
+ d_r = floor(r/2) * floor((r-1)/2)
+ = C(floor(r/2), 2) + C(ceil(r/2), 2),
+where C(n,2) = n(n-1)/2 is "n choose 2".
+
+ THEOREM (Zarankiewicz conjecture). For all m, n >= 1,
+ cr(K_{m,n}) = d_m * d_n.
+
+The rest of the document proves this completely.
+
+2. THE d-SEQUENCE AND SMALL CASES
+
+2.1 Values. The Zarankiewicz numbers satisfy
+ d_{2s} = s(s-1),
+ d_{2s+1} = s^2.
+Specifically:
+ r: 1 2 3 4 5 6 7 8 9 10
+ d_r: 0 0 1 2 4 6 9 12 16 20
+
+2.2 Small cases, all consistent with the theorem.
+ cr(K_{1,n}) = 0 (a star; planar)
+ cr(K_{2,n}) = 0 (a double fan; planar)
+ cr(K_{3,3}) = 1 (three houses, three utilities:
+ K_{3,3} is nonplanar, but one crossing
+ achieves it)
+ cr(K_{4,4}) = 4 (Kleitman 1970)
+ cr(K_{7,7}) = 81 (Woodall 1993, by computer search)
+
+2.3 Background. Turan posed the brick-factory problem around 1944.
+Zarankiewicz (1955) built the balanced-axis drawing (Section 4) and
+claimed optimality, but his argument had a gap. For seventy years no
+one closed it. Even the previous best asymmetric lower bound, by
+Balogh, Lidicky, Norin, Pfender, Salazar and Spiro (2023), reached only
+cr(K_{n,n}) >= 0.9118 * d_n^2 + o(n^4) - close but not exact. This
+document gives the exact formula with a complete proof.
+
+3. THE PLAN
+
+3.1 Two inequalities suffice.
+ Upper bound: cr(K_{m,n}) <= d_m d_n. Exhibit ONE drawing.
+ Lower bound: cr(K_{m,n}) >= d_m d_n. Show EVERY drawing crosses
+ at least d_m d_n times.
+
+3.2 The upper bound is a specific construction (Section 4).
+The lower bound is hard: no matter how cleverly you bend the edges,
+the crossing count cannot drop below d_m d_n. We prove it by turning
+the geometry into linear algebra:
+
+ (a) From any drawing, build a signed crossing matrix J whose
+ entries are signed intersection numbers of oriented edges.
+ (b) Closed loops give linear relations ("cycle pairing"). This
+ makes every block-difference J^{ik} - J^{i1} - J^{1k} + J^{11}
+ "additive" (row plus column).
+ (c) A linear map Phi (called the rank detector) sends each block
+ J^{ik} to a matrix R_ik = X_i - Y_k, with X_i - Y_i
+ invertible.
+ (d) A linear-algebra inequality (Section 8) forces
+ sum_{i != k} rank(R_ik) >= 2 d_m d_n.
+ (e) Each off-diagonal R_ik is bounded by the crossing count c_ik
+ between stars i and k.
+ (f) So 2 c(D) = sum c_ik >= sum rank(R_ik) >= 2 d_m d_n.
+
+3.3 Roadmap.
+ Sections 6-8 linear algebra.
+ Sections 9-12 geometry of drawings, cycle pairing, block
+ additivity.
+ Sections 13-15 the detector Phi.
+ Section 16 odd n finishing.
+ Section 17 even n via vertex deletion.
+ Section 18 normalization of arbitrary drawings.
==============================================================================
-PART III THE ALGEBRAIC TOOLS
+PART II THE UPPER BOUND
==============================================================================
-7. A LINEAR ALGEBRA CRASH COURSE
-------------------------------------------------------------------------------
-
-7.1 Vector spaces. A vector space over the real numbers is a set V with
-two operations (addition of two elements, and multiplication of an
-element by a real number) obeying the obvious arithmetic rules. Examples:
-R^n (all n-tuples of reals) and R^{a x b} (all a-by-b real matrices,
-with entrywise operations).
-
-7.2 Dimension. A list v_1, ..., v_k in V is INDEPENDENT if the only
-way c_1 v_1 + ... + c_k v_k = 0 (with c_i real) is all c_i = 0. A
-BASIS is an independent list that SPANS V (every vector is a combination
-of them). Any two bases of the same vector space have the same length;
-that common length is the DIMENSION. For R^n, dim = n.
-
-7.3 Subspaces. A SUBSPACE of V is a subset U that is itself a vector
-space (closed under addition and scalar multiplication, contains 0).
-For subspaces U, V of W, the INTERSECTION
-
- U cap V = {w in W : w in U and w in V}
-
-and the SUM
-
- U + V = {u + v : u in U, v in V}
-
-are again subspaces.
-
-7.4 Linear maps. T : V -> W is LINEAR if T(a + b) = T(a) + T(b) and
-T(c a) = c T(a) for all vectors and scalars. The KERNEL of T is
-{v : T(v) = 0}; it is a subspace of V. The IMAGE is {T(v) : v in V};
-it is a subspace of W. The RANK-NULLITY theorem says
-
- dim(kernel T) + dim(image T) = dim(V).
-
-7.5 Matrices as linear maps. A matrix M with columns and rows acts on
-column vectors by x -> M x. Under this identification:
-
- rank(M) = dim(image of M) = the largest size of a square
- submatrix with nonzero determinant.
- nullity(M) = dim(kernel of M) = (number of columns) - rank(M).
-
-For a SQUARE d-by-d matrix M, rank M <= d; rank M = d iff M is
-INVERTIBLE (there is N with MN = NM = identity).
-
-7.6 Rank facts. For matrices A, B of matching shapes:
-
- rank(A + B) <= rank(A) + rank(B) (subadditivity)
- rank(A B) <= min(rank(A), rank(B)) (submultiplicativity).
-
-Both follow from elementary dimension counting.
-
-7.7 Vector spaces of matrices. R^{d x d} is a vector space of
-dimension d^2. Any LINEAR map T from R^{d x d} to R^{e x e} is determined
-by its values on the d^2 "standard" matrices E_{pq} (1 in position
-(p,q), 0 elsewhere):
-
- T(M) = sum_{p,q} M[p,q] * T(E_{pq}).
-
-We will build one such T (the "detector") in Section 16.
-
-7.8 Quotients. If U is a subspace of W, the QUOTIENT SPACE W/U is the
-set of equivalence classes {w + U : w in W} under the rule "two vectors
-are equivalent if their difference lies in U". It has dimension
-dim W - dim U. The QUOTIENT MAP pi : W -> W/U sends w to its class,
-with kernel exactly U. This appears in Section 8.
-
-7.9 Polynomials. A real POLYNOMIAL is f(t) = c_0 + c_1 t + ... + c_k t^k
-for real coefficients. Its DEGREE is the largest k with c_k != 0. FACT:
-a nonzero polynomial of degree d has at most d distinct real roots. So
-if it vanishes at d+1 distinct numbers, it is the zero polynomial.
-
-7.10 That's all we need. Every heavy tool below reduces to linear maps,
-dimensions, kernels, ranks, and "a nonzero degree-d polynomial has at
-most d roots."
-
-8. THE SUBSPACE INTERSECTION LEMMA
-------------------------------------------------------------------------------
-
-8.1 Statement. Fix m >= 1, and let W be a real vector space of
-dimension N. Let U_1, ..., U_m and V_1, ..., V_m be subspaces of W.
-Suppose for each i
-
- U_i cap V_i = {0}.
-
-Then
-
- sum_{i,j = 1}^{m} dim(U_i cap V_j) <= floor(m^2 / 4) * N.
-
-8.2 Sanity check. For m = 1, floor(1/4) = 0, and indeed U_1 cap V_1 =
-{0}. For m = 2, floor(4/4) = 1, so total dim <= N. For m = 3,
-floor(9/4) = 2, total <= 2N. For m = 4, floor(16/4) = 4, total <= 4N.
-
-8.3 Sharpness. Split W = P + Q (direct sum) with dim P + dim Q = N.
-Divide indices 1, ..., m into groups of sizes a = floor(m/2) and
-b = ceil(m/2). For i in the first group set (U_i, V_i) = (P, Q); for i
-in the second group set (U_i, V_i) = (Q, P). Then U_i cap V_i = {0} for
-every i. But if i is in group 1 and j is in group 2 (or vice versa), U_i
-cap V_j = P (or Q, respectively). Totaling: a * b * (dim P + dim Q) =
-floor(m^2/4) * N. So the constant is exact.
-
-8.4 Proof (first half: a polynomial filtration). Choose distinct real
-numbers t_1, ..., t_m ("nodes"). For a subspace Z of W (any subspace,
-not just the given U_i, V_i) and an integer h >= 0, define
-
- P_h(Z) = { p in Z[xi] : deg p <= h,
- and p(t_i) lies in U_i for every i }.
-
-Here Z[xi] means "polynomials xi -> sum_e z_e xi^e with vector
-coefficients z_e in Z". Since Z is a subspace of W, each p(t_i) is a
-vector in W, and the constraint "p(t_i) in U_i" is a subspace condition.
-Put P_{-1}(Z) = {0}.
-
-Also set
-
- E_h(Z; t) = { p(t) : p in P_h(Z) } for t real,
- k_h(Z) = dim P_h(Z) - dim P_{h-1}(Z).
-
-8.5 Evaluation away from the nodes. Claim: for real t not in
-{t_1, ..., t_m},
-
- dim E_h(Z; t) = k_h(Z).
-
-Reason. Consider the evaluation map ev_t : P_h(Z) -> W, p |-> p(t). Its
-kernel is precisely (xi - t) * P_{h-1}(Z): if p(t) = 0 then p(xi) is
-divisible by xi - t (as a vector polynomial with coefficients in Z;
-division preserves Z because t is a real scalar), and conversely. The
-kernel is isomorphic to P_{h-1}(Z), so dim kernel = dim P_{h-1}(Z).
-Rank-nullity gives
-
- dim(image ev_t) = dim P_h(Z) - dim P_{h-1}(Z) = k_h(Z).
-
-8.6 The filtration sums to the diagonal. Claim:
-
- sum_{h=0}^{m-1} k_h(Z) = sum_{i=1}^{m} dim(U_i cap Z).
-
-Reason. The left side telescopes to dim P_{m-1}(Z). Now: evaluation at
-all nodes, ev_{t_1}, ..., ev_{t_m}, defines a linear map
-
- P_{m-1}(Z) -> prod_{i=1}^{m} (U_i cap Z).
-
-Why U_i cap Z? Because p in Z[xi] means p(t_i) in Z as well as in U_i
-by the constraint. Conversely, given any (z_1, ..., z_m) with z_i in
-U_i cap Z, the Lagrange interpolation polynomial
-
- p(xi) = sum_i z_i * prod_{k != i} (xi - t_k) / (t_i - t_k)
-
-has degree <= m-1, lies in Z[xi] (since z_i in Z and scalars), and
-satisfies p(t_i) = z_i. Uniqueness: if p in P_{m-1}(Z) vanishes at all
-m nodes, it is a degree <= m-1 polynomial with m distinct roots, hence
-zero. So both dimensions agree.
-
-8.7 Proof (second half: rank losses at nodes). Fix a real number t_*
-outside the node set. The nested spaces E_0(W;t_*) <= E_1(W;t_*) <= ...
-<= E_{m-1}(W;t_*) have successive dimensions
-
- l_h = k_h(W) - k_{h-1}(W) >= 0.
-
-At stage h, choose l_h polynomials from P_h(W) whose values at t_*
-extend the previously chosen columns to a basis of E_h(W; t_*). Fix
-coordinates on W, and let M_h(xi) be the matrix (columns = chosen
-polynomials evaluated at xi, through stage h) with r_h = k_h(W)
-columns. These columns are independent at t_*, so some r_h-row minor
-Delta_h(xi) has Delta_h(t_*) != 0.
-
-Degree bound. Every column chosen at stage e has degree <= e. Expanding
-the determinant as a signed sum over permutations, we get
-
- deg Delta_h <= sum_{e=0}^{h} e * l_e.
-
-Rank loss at a node. For j in {1, ..., m}, let pi_j : W -> W/V_j be
-the quotient map. Claim:
-
- dim E_h(W; t_j) <= k_h(W) - k_h(V_j).
-
-Reason. At a non-node t, the kernel of pi_j on E_h(W; t) contains
-E_h(V_j; t), so dim pi_j(E_h(W; t)) <= dim E_h(W; t) - dim E_h(V_j; t)
-= k_h(W) - k_h(V_j). This "polynomial in t" rank bound extends to
-t = t_j by continuity (every minor larger than the bound vanishes at
-infinitely many t, hence identically, hence also at t_j). But E_h(W;t_j)
-is contained in U_j (by the constraint at t_j), and pi_j is injective on
-U_j because U_j cap V_j = {0}. So dim E_h(W;t_j) = dim pi_j(E_h(W;t_j))
-<= k_h(W) - k_h(V_j).
-
-Multiplicity. The chosen columns at t_j lie in E_h(W;t_j), and restricting
-to r_h rows can only lower rank. Hence the square matrix defining Delta_h
-has nullity at least k_h(V_j) at t_j, so its determinant is divisible by
-(xi - t_j)^{k_h(V_j)}. Applying this separately at the m distinct nodes
-gives
-
- prod_{j=1}^{m} (xi - t_j)^{k_h(V_j)} divides Delta_h(xi).
-
-Delta_h is nonzero (since Delta_h(t_*) != 0), so its degree is at least
-the degree of the divisor:
-
- sum_{j=1}^{m} k_h(V_j) <= sum_{e=0}^{h} e * l_e.
-
-8.8 Summing degree bounds. Sum the last inequality over h =
-0,...,m-1:
-
- sum_{h=0}^{m-1} sum_{j=1}^{m} k_h(V_j)
- <= sum_{h=0}^{m-1} sum_{e=0}^{h} e * l_e.
-
-Left side, by 8.6 with Z = V_j: sum_h k_h(V_j) = sum_i dim(U_i cap V_j),
-and then summing over j gives sum_{i,j} dim(U_i cap V_j).
-
-Right side: interchange sums (each l_e appears with coefficient e for
-each h in {e, ..., m-1}, so m - e times):
-
- right = sum_{e=0}^{m-1} e (m - e) * l_e
- <= floor(m^2/4) * sum_{e=0}^{m-1} l_e
- <= floor(m^2/4) * dim E_{m-1}(W; t_*)
- <= floor(m^2/4) * N.
-
-The first <= uses the elementary bound e(m-e) <= floor(m^2/4) for
-0 <= e <= m. The second uses sum_e l_e = k_{m-1}(W) = dim E_{m-1}(W;t_*).
-The last uses E_{m-1}(W;t_*) <= W, of dimension N. Done.
-
-9. RANKS OF MATRIX DIFFERENCES
-------------------------------------------------------------------------------
-
-9.1 Corollary (rank-sum for differences). Let X_1, ..., X_m and
-Y_1, ..., Y_m be d-by-d real matrices. Suppose X_i - Y_i is INVERTIBLE
-for every i. Then
-
- sum over ORDERED pairs (i,j) with i != j of rank(X_i - Y_j)
- >= 2 * d_m * d, where d_m = floor(m/2) * floor((m-1)/2).
-
-9.2 Proof. Work in W = R^d + R^d (direct sum), dim W = 2d. For each i
-define the subspace
-
- U_i = { (v, X_i v) : v in R^d } (the GRAPH of v |-> X_i v)
- V_j = { (v, Y_j v) : v in R^d } (the GRAPH of v |-> Y_j v).
-
-Both have dimension d. Their intersection is
-
- U_i cap V_j = { (v, X_i v) : X_i v = Y_j v for some v }
- = { (v, X_i v) : v in kernel(X_i - Y_j) },
- dim(U_i cap V_j) = dim kernel(X_i - Y_j) = d - rank(X_i - Y_j).
-
-For i = j, X_i - Y_i is invertible, so rank(X_i - Y_i) = d and
-dim(U_i cap V_i) = 0. Applying Lemma 8.1 with N = 2d:
-
- sum_{i,j} dim(U_i cap V_j) <= floor(m^2/4) * 2d.
-
-Writing S = sum_{i,j} rank(X_i - Y_j), the left side is m^2 d - S.
-Hence
-
- S >= d * (m^2 - 2 floor(m^2/4)).
-
-The diagonal terms contribute m * d, and dividing by that leaves the
-off-diagonal sum >= d * (m^2 - m - 2 floor(m^2/4)). A short computation:
-
- m = 2r: m^2 - m - 2 floor(m^2/4) = 2r(r-1) = 2 d_m
- m = 2r+1: m^2 - m - 2 floor(m^2/4) = 2r^2 = 2 d_m
-
-so the off-diagonal sum is at least 2 d_m d. Done.
-
-9.3 Example. m = 4, d_m = 2. Bound: at least 4d off-diagonal rank,
-summed over 12 off-diagonal ordered pairs. In our application each term
-rank(X_i - Y_j) will be bounded by the crossing count c_{ij}, and the
-sum of those c_{ij} over ordered pairs i != j equals 2 c(D). Combining
-gives 2 c(D) >= 4d, i.e. c(D) >= 2d, which exactly matches cr(K_{4,n})
->= d_4 * d_n for the odd case n = 2s+1 (where d = d_n = s^2).
-
-9.4 Why this is the right tool. Everything now reduces to producing
-matrices X_i - Y_j whose off-diagonal ranks are each controlled by the
-corresponding crossing count c_{ik}, and whose diagonal entries remain
-invertible. That is the role of Sections 10-18.
+4. THE BALANCED-AXIS DRAWING
+
+4.1 Goal. Draw K_{m,n} with exactly d_m d_n crossings.
+
+4.2 Construction. Set
+ u = floor(m/2), u' = m - u = ceil(m/2),
+ v = floor(n/2), v' = n - v = ceil(n/2).
+Place:
+ u A-vertices on the positive y-axis,
+ u' A-vertices on the negative y-axis,
+ v B-vertices on the positive x-axis,
+ v' B-vertices on the negative x-axis.
+Draw every edge as a straight segment. All positions distinct, none at
+the origin.
+
+4.3 Crossings in the NE quadrant. An edge lies in the open quadrant
+x>0, y>0 iff its A-endpoint is one of the upper vertices and its
+B-endpoint is one of the right vertices.
+
+Fix two upper A-vertices and two right B-vertices. The four points lie
+on the two positive coordinate axes, forming a convex quadrilateral.
+Its two diagonals each join an A-vertex to a B-vertex, so both are
+edges of K_{m,n}; diagonals of a convex quadrilateral cross exactly
+once, so these two edges cross inside the quadrant. Conversely every
+NE crossing arises as the "diagonal pairing" of some choice of two
+A-vertices and two B-vertices. (Which of the two possible pairings is
+the diagonal one depends on the relative orders of the four points
+along the two axes, but exactly one always is.)
+
+So the number of NE-quadrant crossings equals
+ C(u, 2) * C(v, 2).
+
+4.4 All four quadrants. Every edge lies in exactly one of the four
+open quadrants. Its A-endpoint has a nonzero y-coordinate, whose sign
+determines upper (positive) or lower (negative); its B-endpoint has a
+nonzero x-coordinate, whose sign determines right (positive) or left
+(negative). Summing contributions:
+ NE: C(u, 2) * C(v, 2)
+ NW: C(u, 2) * C(v', 2)
+ SE: C(u', 2) * C(v, 2)
+ SW: C(u', 2) * C(v', 2)
+Total:
+ (C(u,2) + C(u',2)) * (C(v,2) + C(v',2)) = d_m * d_n,
+using C(floor(r/2),2) + C(ceil(r/2),2) = d_r.
+
+4.5 Why balanced split. With u + u' = m fixed, C(u,2) + C(u',2) is a
+convex quadratic in u minimized at u = m/2. Hence the balanced split
+u = floor(m/2), u' = ceil(m/2) is optimal. Same for v, v'.
+
+4.6 Triple crossings. Three of the straight segments could conceivably
+concur at one point. For fixed m,n that concurrence is a polynomial
+condition on the axis coordinates. The set of positions avoiding all
+such triple events is dense and open, so a small generic perturbation
+removes all triple events without changing any of the double crossings
+(the double crossings are stable). Therefore an admissible drawing
+with exactly d_m d_n crossings exists.
+
+4.7 Conclusion. cr(K_{m,n}) <= d_m d_n. If m <= 2 or n <= 2 then
+d_m d_n = 0, matching the trivial lower bound.
==============================================================================
-PART IV THE GEOMETRIC MACHINERY
+PART III THE PLAN FOR THE LOWER BOUND
==============================================================================
-10. SIGNED INTERSECTIONS OF ORIENTED EDGES
-------------------------------------------------------------------------------
-
-10.1 Setup. Fix a minimum drawing D of K_{m,n}. By the drawing
-normalization lemma (Section 20), we may assume D is polygonal, straight
-near every vertex and every crossing, and no two edges with a common
-endpoint cross. That last property is why "adjacent" edges never
-contribute crossings; but they still contribute to the local order
-signs defined below.
-
-10.2 Fixed edge orientations. Orient every edge a_i b_p FROM a_i TO b_p.
-This is called the FIXED orientation.
-
-10.3 Signed intersections of edges. For two oriented edges e, f,
-define I(e, f) as the sum of the SIGNS of all their interior crossings:
-
- I(e, f) = sum over interior crossings of e and f of
- (+1 if e's direction to f's direction is CCW, else -1).
-
-Concretely: write u = direction of e, v = direction of f at a crossing.
-The sign is the sign of the 2x2 determinant det(u, v). Set I(e, e) = 0.
-
-Immediate facts:
-
- I(e, f) = -I(f, e) (swapping reverses the determinant sign).
-
- I(e, f) has the same parity as the (unsigned) number of crossings.
-
-10.4 Spoke orders at a vertex. At a vertex v, choose a "cut" between
-two consecutive outward spokes of v (the edges leaving v). Starting
-from the cut, list all edges at v counterclockwise. For two edges
-e, f incident with v define
-
- T_v(e, f) = +1 if e precedes f in that list,
- T_v(e, f) = -1 if f precedes e,
- T_v(e, f) = 0 if e = f.
-
-Also define
-
- sigma_{v,e} = +1 if e is oriented OUT of v,
- sigma_{v,e} = -1 if e is oriented INTO v.
-
-Consequence for the fixed orientations: at every a_i, sigma = +1. At
-every b_p, sigma = -1. So a product sigma sigma at a shared a_i is
-+1, at a shared b_p is +1 (minus times minus).
-
-10.5 The matrix J. For any two edges e, f of K_{m,n}, set
-
- J(e, f) = I(e, f)
- + (1/2) sum over v that is an endpoint of both e and f
- of sigma_{v,e} sigma_{v,f} T_v(e, f).
-
-The half-order term is "on" only when e and f share a vertex. Reading
-off the four cases:
-
- i = k, p = q: J(e, e) = 0.
- i = k, p != q: J = I + (1/2) T_{a_i}(e, f).
- i != k, p = q: J = I + (1/2) T_{b_p}(e, f).
- i != k, p != q: J = I.
-
-10.6 Antisymmetry. Since I and T are both antisymmetric (T_v(e, f)
-= -T_v(f, e)) and diagonal entries are zero, the matrix J is
-ANTISYMMETRIC: J(e, f) = -J(f, e).
-
-10.7 Block decomposition. Number the edges as e_{ip} = edge a_i b_p.
-Group the edges by i, giving m blocks of n edges each. Then J is an
-mn-by-mn matrix, split into n-by-n blocks:
-
- J^{ik}(p, q) = J(e_{ip}, e_{kq}).
-
-The diagonal blocks have a special shape:
-
- J^{ii}(p, q) = (1/2) T_{a_i}(e_{ip}, e_{iq}) for p != q,
- J^{ii}(p, p) = 0.
-
-This is exactly HALF the sign matrix of the counterclockwise spoke order
-at a_i. Recall the definition in the introduction: S_prec(p,q) = +1/2
-if p precedes q in the order, -1/2 if q precedes p, 0 on the diagonal.
-So J^{ii} = S_prec for the spoke order at a_i.
-
-That is why our detector Phi will have to send S_prec to an invertible
-matrix: it will need to send J^{ii} to something invertible.
-
-11. THE CHORD FORMULA
-------------------------------------------------------------------------------
-
-11.1 Two oriented chords in a disk. Let C and E be two oriented straight
-chords of a round disk whose four boundary endpoints are distinct.
-
-For chord C, define its ENDPOINT COEFFICIENTS
-
- eps_C(u) = -1 if u is the START of C,
- eps_C(u) = +1 if u is the END of C,
- eps_C(u) = 0 if u is not an endpoint of C.
-
-Same for chord E.
-
-11.2 Cut and comparison sign. Place a "cut" in the boundary circle,
-away from all four endpoints. For two boundary points u, w define
-
- T(u, w) = +1 if u precedes w counterclockwise from the cut,
- T(u, w) = -1 if w precedes u.
-
-11.3 Chord formula. The signed intersection of the two oriented chords
-equals
-
- I(C, E) = (1/2) sum_{u in {start_C, end_C}}
- sum_{w in {start_E, end_E}}
- eps_C(u) eps_E(w) T(u, w).
-
-11.4 Proof. First, the right-hand side is independent of the cut
-position. Reason: sliding the cut past a boundary point shifts T(u, w)
-by a multiple of the number of boundary points. Formally, when the cut
-passes an endpoint u_0 of C, the sum changes by a constant times
-sum_w eps_E(w) = (+1) + (-1) = 0. Same when it passes an endpoint of E.
-So we may place the cut wherever convenient.
-
-Place the cut just before start_C. Then the counterclockwise boundary
-order begins
-
- start_C, (some arc), end_C, (the rest of the circle), back to start_C.
-
-For u = start_C: start_C is first in CCW order, so T(start_C, w) = +1
-for both w. Contribution:
-
- (1/2) * eps_C(start_C) * sum_w eps_E(w) * (+1)
- = (1/2) * (-1) * (+1 + (-1)) * (+1) = 0.
-
-For u = end_C: T(end_C, w) = -1 if w precedes end_C on the arc from
-start_C to end_C, and T(end_C, w) = +1 if w is on the other arc. So
-
- contribution = (1/2) * (+1) *
- ( -sum_{w on arc start_C->end_C} eps_E(w)
- + sum_{w on the other arc} eps_E(w) ).
-
-But the "other arc" and the "first arc" partition all four endpoints
-of E, and eps_E sums to zero over any pair, so their sums are negatives
-of each other. Therefore
-
- I(C, E) = - sum_{w on the open CCW arc from start_C to end_C}
- eps_E(w).
-
-This is the working formula.
-
-11.5 What the formula says. Two cases.
-
-Case A ("nonalternating"): both endpoints of E lie on the SAME arc
-determined by C. Then the sum over the arc is either eps_E + eps_E = 0,
-or 0. Either way I(C, E) = 0. Nonalternating = no crossing.
-
-Case B ("alternating"): one endpoint of E is on the arc from start_C
-to end_C, the other on the other arc. Then the formula picks up just
-one eps_E value, giving +1 or -1. Matches the geometric picture (chords
-cross, sign depends on orientations).
-
-11.6 Two examples.
-
-Example 1: CCW order is start_C, start_E, end_C, end_E.
- Arc(start_C -> end_C) contains start_E.
- eps_E(start_E) = -1.
- I(C, E) = -(-1) = +1. Positive crossing.
-
-Example 2: CCW order is start_C, end_E, end_C, start_E.
- Arc(start_C -> end_C) contains end_E.
- eps_E(end_E) = +1.
- I(C, E) = -(+1) = -1. Negative crossing.
-
-Good: reversing one chord's orientation reverses the crossing sign. That
-matches I(e, f) = -I(f, e).
-
-11.7 Why we need this. In the next section we will replace a shared
-vertex disk by chords and use this formula to extract exactly the
-half-order local term. The 1/2 factor in J comes from averaging over
-"left shift" and "right shift" versions of a cycle's track.
-
-12. CYCLE PAIRING LEMMA
-------------------------------------------------------------------------------
-
-12.1 Cycle vectors. A CYCLE of K_{m,n} is a closed walk that visits
-no vertex twice except at its starting point. Orient the walk (choose a
-direction to travel). Its CYCLE VECTOR z in R^{E(K_{m,n})} is
-
- z_e = +1 if e is traversed in the fixed orientation,
- z_e = -1 if e is traversed against it,
- z_e = 0 if e is not used.
-
-A simple cycle has coordinates in {-1, 0, +1}.
-
-12.2 Lemma (cycle pairing). For any two oriented simple cycles of
-K_{m,n} with cycle vectors z, y in R^{E(K_{m,n})},
-
- z^T J y = 0.
-
-The cycles may share vertices and edges, and may traverse a shared edge
-in opposite directions.
-
-12.3 Proof.
-
-Step 1 (first cycle -> closed polygonal walk). Around each vertex of
-the first cycle draw a small round disk, all disks pairwise disjoint
-and meeting the drawing only in straight spokes. Inside each disk,
-replace the two incident spokes of the first cycle by the chord
-joining their two boundary endpoints. Outside the disks, keep the
-original tracks. The result is a closed polygonal walk gamma; it may
-self-intersect. Its traversal-signed edge weights are z.
-
-Step 2 (second cycle -> two shifted walks). Similarly place small disks
-at each crossing and bend of the second cycle. Between disks the second
-cycle is a union of straight pieces. SHIFT each straight piece a tiny
-distance perpendicular to itself: either always to the LEFT (relative
-to its own direction) or always to the RIGHT. Inside each disk join
-shifted ends by a short arc, without changing the disk interior. This
-gives two closed polygonal walks eta_+ (left shift) and eta_- (right
-shift), both with traversal-signed edge weights y. Choose the shift so
-small that:
-
- - in each crossing disk, a shifted track of the second cycle still
- meets exactly one unshifted track of the first, with the same
- sign of crossing;
-
- - in each vertex disk that both cycles visit, the two shifted copies
- of a shared spoke boundary point lie on OPPOSITE sides of the
- unshifted endpoint (so their order signs cancel in the average).
-
- (This is exactly why T_v(e, e) = 0 makes the local term equal to 1/2
- sum sigma sigma T for distinct spokes, and zeroes for equal ones.)
-
-Step 3 (total signed intersection of two closed walks is zero). Take
-the closed polygonal walk gamma and cone it to a point O outside
-everything (using oriented triangles O-u-w for each segment u->w of
-gamma). Each triangle boundary has zero total signed intersection with
-eta: every entrance into the triangle is paired with an exit. Adding
-all triangles: cone segments cancel, leaving exactly the original walk
-gamma. So gamma and eta have zero total signed intersection. The
-argument counts traversal signs and works even for non-simple walks.
-
-Step 4 (combine). For each eta in {eta_+, eta_-}, the total signed
-intersection of gamma with eta is zero. This splits into
-
- (sum over exterior crossings) + (sum over vertex-disk crossings)
- = 0.
-
-The exterior part is the sum over pairs of edges used by z and y of
-z_e y_f I(e, f). It does not depend on the sign of the shift.
-
-The vertex-disk part at each shared vertex v equals
-
- (1/2) sum over (e,f) used by z,y with both incident to v of
- sigma_{v,e} sigma_{v,f} T_v(e,f) z_e y_f.
-
-The 1/2 comes from averaging eta_+ and eta_- contributions: each gives
-a T_v(e,f) term, and their average over the two shifts is what the
-antisymmetric T_v(e,e) = 0 convention encodes.
-
-Adding everything gives
-
- 0 = z^T I y + (1/2) sum over shared v, edges e,f of
- sigma sigma T z_e y_f
- = z^T J y.
-
-Done.
-
-12.4 Remark. The 1/2 in the definition of J is exactly the coefficient
-from averaging the two shifts. Without it, the local term would not
-match; with it, cycle pairing holds for all order choices.
-
-12.5 Application. We will apply Lemma 12.2 to 4-cycles. This gives
-the block relation of Section 13.
-
-13. ADDITIVE BLOCK RELATION
-------------------------------------------------------------------------------
-
-13.1 Additive (= row-plus-column) matrices. A matrix H in R^{n x n}
-is ADDITIVE if there exist vectors r, c in R^n with
-
- H(p, q) = r_p + c_q for all p, q.
-
-Characterization. H is additive iff for all row indices p, p' and
-column indices q, q',
-
- H(p,q) - H(p,q') - H(p',q) + H(p',q') = 0.
-
-Proof. If H(p,q) = r_p + c_q, the four-term alternating sum is
-(r_p + c_q) - (r_p + c_q') - (r_p' + c_q) + (r_p' + c_q') = 0.
-Conversely, if the four-term identity always holds, fix p_0 = q_0 = 1
-and set r_p = H(p, 1), c_q = H(1, q) - H(1, 1). Then
-
- H(p, q) = H(p, 1) + H(1, q) - H(1, 1) = r_p + c_q.
-
-13.2 Statement of block additivity. For any 1 <= i, k <= m, the block
-
- H(i, k) = J^{ik} - J^{i1} - J^{1k} + J^{11} (an n-by-n matrix),
-
-is additive.
-
-13.3 Proof. Fix i, k. If i = 1, then H(1, k) = J^{1k} - J^{11} - J^{1k} +
-J^{11} = 0, which is additive. Same if k = 1. So assume i, k >= 2.
-Also, if p = p' or q = q', the four-term alternating sum for H(i,k) is
-trivially zero (two identical terms cancel). So assume p != p', q != q'.
-
-Build the 4-cycle in the first-layer K_{m,*}:
-
- gamma_A: a_i -> b_p -> a_1 -> b_{p'} -> a_i.
-
-Fixed orientations go a_i -> b_p and a_1 -> b_p, etc. Checking each
-edge traversal against its fixed orientation:
-
- e_{ip}: traversed a_i -> b_p, matching fixed orientation. z_{ip} +1.
- e_{1p}: traversed b_p -> a_1, against fixed (a_1 -> b_p). z_{1p} = -1.
- e_{1p'}: traversed a_1 -> b_{p'}, matching. z_{1p'} = +1.
- e_{ip'}: traversed b_{p'} -> a_i, against. z_{ip'} = -1.
-
-So z with z_{ip} = z_{1p'} = +1 and z_{ip'} = z_{1p} = -1.
-
-Similarly, the 4-cycle gamma_B: a_k -> b_q -> a_1 -> b_{q'} -> a_k,
-so y with y_{kq} = y_{1q'} = +1, y_{kq'} = y_{1q} = -1.
-
-By Lemma 12.2, z^T J y = 0. Expanding the 16 terms and regrouping by
-H entries:
-
- 0 = z^T J y
- = J(ip,kq) - J(ip,1q) - J(ip,kq') + J(ip,1q')
- + J(1p',kq) - J(1p',1q) - J(1p',kq') + J(1p',1q')
- - J(ip',kq) + J(ip',1q) + J(ip',kq') - J(ip',1q')
- - J(1p,kq) + J(1p,1q) + J(1p,kq') - J(1p,1q')
- = H(p,q) - H(p,q') - H(p',q) + H(p',q').
-
-So H satisfies the characterization from 13.1. Therefore H(i,k) is
-row-plus-column. Done.
-
-13.4 Consequence: the difference form. Let Phi be ANY linear map from
-n-by-n matrices to d-by-d matrices that annihilates all additive
-matrices (i.e., all H with H(p,q) = r_p + c_q). Applying Phi to 13.2:
-
- Phi(J^{ik}) - Phi(J^{i1}) - Phi(J^{1k}) + Phi(J^{11}) = 0.
-
-Set R_ik = Phi(J^{ik}), X_i = R_i1, Y_k = R_11 - R_1k. Then
-
- R_ik = X_i - Y_k.
-
-Verification: rewriting the equation above, R_ik = R_i1 + R_1k - R_11
-= X_i - (R_11 - R_1k) = X_i - Y_k.
-
-13.5 Diagonal invertibility. Take k = i. The same equation gives
-
- X_i - Y_i = R_ii = Phi(J^{ii}).
-
-But J^{ii} is exactly the spoke-order matrix S_prec of a_i (Section
-10.7). So if our Phi sends S_prec to an invertible matrix (as the
-detector will guarantee), then X_i - Y_i is invertible for every i,
-which is the hypothesis of the rank-sum corollary (9.1). Perfect.
-
-13.6 What remains. We need to construct a linear map Phi : R^{n x n}
--> R^{d x d} (d = d_n) with the following three properties, for a
-suitable choice of d = s^2 when n = 2s + 1 is odd.
-
- (i) Phi annihilates every additive matrix.
- (ii) Phi sends each "elementary" matrix E_{pq} (1 in (p,q),
- 0 elsewhere) to a matrix of rank <= 1.
- (iii) Phi sends S_prec to an invertible matrix, for EVERY strict
- total order prec on {1, ..., n}.
-
-Property (i) makes the difference form work. Property (ii) will let us
-bound the rank of Phi(J^{ik}) by the number of crossings c_ik (Section
-18). Property (iii) makes X_i - Y_i invertible, so the rank-sum
-corollary applies.
-
-The construction uses Lagrange interpolation and the two-triangle
-pattern. Both are spelled out in Sections 14-17. Done with Part IV.
+5. STRATEGY
+
+5.1 Fix m,n and a MINIMUM drawing D of K_{m,n}. By Section 18, D may
+be assumed polygonal, straight near every vertex and crossing, with
+ no crossing between edges that share a vertex.
+We call these "adjacent edges", and they never cross in a normalized
+drawing.
+
+5.2 Three ingredients.
+
+ (GEOMETRY) Signed crossing matrix J with n x n blocks J^{ik},
+ satisfying
+ J^{ik} - J^{i1} - J^{1k} + J^{11} is additive.
+ [Sections 9-12]
+
+ (DETECTOR) Linear Phi : R^{n x n} -> R^{d x d} with:
+ Phi(H) = 0 for additive H and diagonal H;
+ Phi(E_pq) has rank <= 1 for every standard matrix E_pq;
+ Phi(S_prec) is invertible for every strict total
+ order prec on {1,...,n}.
+ [Sections 13-15]
+
+ (ALGEBRA) If X_1,...,X_m and Y_1,...,Y_m are d-by-d with every
+ X_i - Y_i invertible, then
+ sum_{i!=k} rank(X_i - Y_k) >= 2 d_m d.
+ [Sections 6-8]
+
+5.3 How they click together. Apply Phi to the blocks of J.
+ Set R_ik = Phi(J^{ik}).
+ Additivity + annihilation:
+ R_ik = Phi(J^{i1}) + Phi(J^{1k}) - Phi(J^{11}) = X_i - Y_k,
+ where X_i = R_i1 and Y_k = R_11 - R_1k.
+ Diagonal: X_i - Y_i = R_ii = Phi(J^{ii}) is invertible by (iii).
+ Off-diagonal: rank(R_ik) <= c_ik.
+ Algebra forces
+ 2 d_m d_n <= sum_{i!=k} rank(R_ik) <= sum_{i!=k} c_ik = 2 c(D).
+
+5.4 Roadmap.
+ Sections 6-8 linear algebra.
+ Sections 9-12 signed intersections and block relations.
+ Sections 13-15 detector.
+ Section 16 odd n done.
+ Section 17 even n reduced to odd n.
+ Section 18 normalization.
==============================================================================
-PART V THE RANK DETECTOR
+PART IV ALGEBRAIC TOOLS
==============================================================================
-14. LAGRANGE INTERPOLATION
-------------------------------------------------------------------------------
-
-14.1 The problem. Given distinct real numbers x_1, ..., x_n and "values"
-y_1, ..., y_n, find a polynomial P(t) of degree <= n-1 with P(x_i) = y_i
-for every i.
-
-14.2 The Lagrange basis. Define, for i = 1, ..., n,
-
- L_i(t) = prod_{k != i} (t - x_k) / (x_i - x_k).
-
-Each L_i is a polynomial of degree exactly n-1 with L_i(x_j) = 1 if i=j
-and 0 otherwise. Therefore
-
- P(t) = sum_{i=1}^{n} y_i * L_i(t)
-
-satisfies P(x_i) = y_i for each i. UNIQUENESS: any two solutions differ
-by a polynomial of degree <= n-1 with n distinct roots, hence zero.
-
-14.3 An explicit form. Let F(t) = prod_k (t - x_k), so F'(x_i) =
-prod_{k != i} (x_i - x_k). Dividing F(t) by (t - x_i) gives a
-polynomial whose value at x_i is F'(x_i). So
-
- L_i(t) = F(t) / ((t - x_i) F'(x_i)).
-
-14.4 Barycentric weights. Define
-
- w_i = 1 / F'(x_i).
-
-These are the "barycentric weights" for the node set {x_1, ..., x_n}.
-They are nonzero (roots are distinct). A crucial, easy-to-derive
-identity:
-
- sum_{i=1}^{n} A(x_i) * w_i = 0 whenever deg A <= n-2.
-
-14.5 Proof of 14.4. Pick a polynomial A of degree <= n-2. On one hand,
-A(t) = sum_i A(x_i) L_i(t) as polynomials (both sides degree <= n-1
-with n matching values). On the other hand, L_i(t) = w_i * prod_{k != i}
-(t - x_k) has leading coefficient w_i. Comparing the coefficients of
-t^{n-1} on both sides:
-
- A side: 0, because deg A <= n-2 < n-1.
- Sum side: sum_i A(x_i) * w_i (each L_i has leading coeff w_i).
-
-So sum_i A(x_i) w_i = 0. Done.
-
-14.6 What we actually use. In Section 16 we will define matrices B_pq
-whose (a,b; a',b') entries look like
-
- (x_p - x_q) * w_p * w_q * x_p^{a + a'} * x_q^{b + b'}.
-
-Summing over q, we want this to vanish. Set A(t) = t^{b + b'}. Its
-degree is b + b' <= 2s - 2 = n - 3 <= n - 2, so 14.4 applies, giving
-sum_q w_q x_q^{b+b'} = 0. Similarly with A(t) = t^{1+b+b'} (degree
-<= 2s - 1 = n - 2), so we also get sum_q w_q x_q^{1+b+b'} = 0. Both
-sums that appear below vanish, which is the magic.
-
-15. TWO-TRIANGLE INTERPOLATION
-------------------------------------------------------------------------------
-
-15.1 The setup. Fix n = 2s+1 distinct real numbers x_1, ..., x_n. A
-BIVARIATE POLYNOMIAL is a function P(u, v) = sum_{a,b} c_{ab} u^a v^b.
-Its BIDEGREE is (deg_u P, deg_v P), the largest a and b with some
-nonzero coefficient.
-
-We focus on bivariate polynomials of bidegree <= (s-1, s-1). They form
-a real vector space B of dimension s * s = s^2 = d. A convenient basis
-is the monomials u^a v^b for 0 <= a, b <= s-1.
-
-15.2 Evaluation vectors. For a pair (p, q), define the "evaluation
-vector" h_pq in R^{s^2} by
-
- h_pq(a, b) = x_p^a * x_q^b for 0 <= a, b <= s-1.
-
-This is the coordinate vector, over the monomial basis u^a v^b, of the
-result of evaluating P at the point (x_p, x_q). Indeed
-
- P(x_p, x_q) = sum_{a,b} c_{ab} * (x_p^a x_q^b) = c^T h_pq.
-
-15.3 The two-triangle pattern Q_s. Let
-
- Q_s = { (p, q) : 1 <= q < p <= s+1 }
- u { (p, q) : s+1 < p < q <= 2s+1 }.
-
-Its size is |Q_s| = s(s+1)/2 + s(s-1)/2 = s^2.
-
-Picture for s = 3 (n = 7). Rows p = 1..7, columns q = 1..7; X marks
-members of Q_s:
-
- p\q 1 2 3 4 5 6 7
- 1 . . . . . . .
- 2 X . . . . . .
- 3 X X . . . . .
- 4 X X X . . . .
- 5 . . . . . X X
- 6 . . . . . . X
- 7 . . . . . . .
-
-The pattern has four distinguishing features:
-
- (a) a FIRST BLUE TRIANGLE in rows 2, 3, 4, columns 1, 2, 3 (down to
- the diagonal, ending at row s+1 = 4, column 1);
-
- (b) an OFF-DIAGONAL GAP at rows 1 and columns >= 4 in the first blue
- section;
-
- (c) a SECOND ORANGE TRIANGLE in rows 5, 6, 7 (right of the main
- diagonal), columns 6, 7;
-
- (d) it TOTAL SIZE s^2 exactly, which is the dimension of B.
-
-15.4 Lemma (two-triangle interpolation). With x_1, ..., x_{2s+1}
-distinct, the s^2 vectors h_pq, (p, q) in Q_s, form a basis of R^{s^2}.
-Equivalently, a bivariate polynomial P of bidegree <= (s-1, s-1) that
-vanishes at all (x_p, x_q) with (p, q) in Q_s is the zero polynomial.
-
-15.5 Proof. Both R^{s^2} and the list {h_pq : (p,q) in Q_s} have size s^2,
-so we just need injectivity: if P has bidegree <= (s-1, s-1) and vanishes
-at all Q_s points, then P = 0. Induction on s.
-
-Base case s = 1: bidegree <= (0, 0), so P is a constant. Q_1 has the
-single point (2, 1). P(x_2, x_1) = 0 means P is constant zero.
-
-Induction step (s >= 2). Take P of bidegree <= (s-1, s-1) vanishing at
-all Q_s points.
-
-Step A: eliminate u - x_{s+1}. The s pairs (s+1, 1), (s+1, 2), ...,
-(s+1, s) all lie in Q_s (since 1 <= q <= s and q < p = s+1). So
-P(x_{s+1}, x_q) = 0 for q = 1, ..., s. View Q_p(v) := P(x_{s+1}, v) as
-a polynomial in v of degree <= s-1. It has the s distinct zeros
-x_1, ..., x_s, so Q_p is the zero polynomial. Therefore
-
- P(u, v) = (u - x_{s+1}) * P_1(u, v),
- deg_u P_1 <= s-2, deg_v P_1 <= s-1.
-
-Step B: eliminate v - x_1. The pairs (p, 1) for p = 2, ..., s lie in
-Q_s (since 1 < p <= s). So P(x_p, x_1) = 0. Since x_p != x_{s+1} for
-p <= s, the factor (x_p - x_{s+1}) is nonzero, so P_1(x_p, x_1) = 0
-for p = 2, ..., s. View P_1(u, x_1) as a polynomial in u of degree
-<= s-2. It has the s-1 distinct zeros x_2, ..., x_s. So P_1 is
-divisible by (v - x_1):
-
- P_1(u, v) = (v - x_1) * R(u, v),
- deg_u R <= s-2, deg_v R <= s-2.
-
-Combining:
-
- P(u, v) = (u - x_{s+1})(v - x_1) * R(u, v).
-
-Step C: What remains of Q_s? Remove the rows p = s+1 already used in
-Step A, and the column q = 1 already used in Step B. The remaining
-points of Q_s are exactly:
-
- A := { (p, q) : 2 <= q < p <= s } (lower triangle in 2..s)
- B := { (p, q) : s+1 < p < q <= 2s+1 } (upper triangle in s+2..2s+1)
-
-At every remaining point (x_p, x_q) in Q_s, we have p != s+1 and q != 1,
-so (x_p - x_{s+1})(x_q - x_1) != 0. Hence R(x_p, x_q) = 0 at every
-(p, q) in A u B.
-
-Step D: change of variable. Define a new node tuple
-
- (y_1, ..., y_{2s-1}) = (x_{s+2}, ..., x_{2s+1}, x_2, ..., x_s).
-
-This list has 2(s-1)+1 = 2s-1 distinct numbers and matches a problem of
-size s - 1. Define S(u, v) = R(v, u). Then S has bidegree
-<= (deg_v R, deg_u R) <= (s-2, s-2) = ((s-1)-1, (s-1)-1).
-
-We claim S vanishes at every point of Q_{s-1} for the y-tuple.
-
- Q_{s-1} = { 1 <= w < r <= s } u { s < r < w <= 2s-1 }
- (using r, w as row/column coordinates).
-
- Recall for r in [1, s]: y_r = x_{s+1+r}.
- Recall for r in [s+1, 2s-1]: y_r = x_{r - s + 1}.
-
- Case 1 (1 <= w < r <= s): y_r = x_{s+1+r}, y_w = x_{s+1+w}.
- So S(y_r, y_w) = R(y_w, y_r) = R(x_{s+1+w}, x_{s+1+r}). Row index
- s+1+w and column index s+1+r. Since 1 <= w < r <= s:
- s+1 < s+1+w < s+1+r <= 2s+1. So (s+1+w, s+1+r) is in B, where R
- vanishes. Good.
-
- Case 2 (s < r < w <= 2s-1): y_r = x_{r - s + 1}, y_w = x_{w - s + 1}.
- So S(y_r, y_w) = R(x_{w - s + 1}, x_{r - s + 1}). Since r < w, the
- column index r - s + 1 < w - s + 1 = row index. And 2 <= r - s + 1
- (since r >= s+1) and w - s + 1 <= s (since w <= 2s-1). So
- (w - s + 1, r - s + 1) is in A, where R vanishes. Good.
-
-So S vanishes on Q_{s-1} for the tuple (y_1, ..., y_{2s-1}). By the
-induction hypothesis, S = 0. Then R = 0, then P = 0. Done.
-
-15.6 Remark. The figure of Section 15.3 is the visual content of this
-lemma. Removing row 4 (the p = s+1 row) and column 1 gives a smaller
-Q_{s-1} on the remaining grid, after a coordinate swap. Every estimate
-in the induction corresponds to a specific row or column of the blue
-and orange triangles.
-
-16. CONSTRUCTING THE RANK DETECTOR
-------------------------------------------------------------------------------
-
-16.1 Goal. For odd n = 2s+1, build a linear map
-
- Phi : R^{n x n} -> R^{s^2 x s^2}
-
-satisfying:
-
- (i) Phi(H) = 0 for every additive matrix H (i.e., H(p,q) = r_p + c_q);
- (ii) Phi(E_pq) has rank <= 1 for all p,q (E_pq = standard matrix);
- (iii) Phi(S_prec) is invertible for every strict linear order prec.
-
-16.2 Master polynomial and barycentric weights. Choose n distinct real
-numbers x_1 < x_2 < ... < x_n. Define
-
- F(t) = prod_{p=1}^{n} (t - x_p),
- w_p = 1 / F'(x_p).
-
-(The ordering x_1 < ... < x_n is for the sign convenience of Step C
-below; invertibility will not depend on the sign.)
-
-16.3 Evaluation vectors and rank-1 blocks. For (p, q) in {1, ..., n}^2,
-let h_pq in R^{s^2} be the s^2-long vector of Section 15.2. Define the
-s^2-by-s^2 matrix
-
- B_pq = (x_p - x_q) * w_p * w_q * (h_pq h_pq^T).
-
-Here h_pq h_pq^T is the OUTER PRODUCT, with entries
-(h_pq h_pq^T)[(a, b), (a', b')] = x_p^{a + a'} x_q^{b + b'}.
-
-Since h_pq != 0 always (its (0, 0) component is 1), B_pq has rank <= 1
-when p != q, and B_pp = 0 (the prefactor x_p - x_p = 0 vanishes).
-
-16.4 Definition of Phi. For any H in R^{n x n}, set
-
- Phi(H) = sum_{p, q = 1}^{n} H(p, q) * B_pq.
-
-This is a linear map R^{n x n} -> R^{s^2 x s^2}. Since the elementary
-matrices E_pq form a basis of R^{n x n}, Phi is uniquely determined by
-
- Phi(E_pq) = B_pq.
-
-16.5 Property (ii) verified. Phi(E_pq) = B_pq has rank <= 1 by Section
-16.3 (rank 1 for p != q; rank 0 for p = q).
-
-16.6 Property (i) verified. Phi annihilates additive matrices.
-
-First, Phi(any diagonal D) = sum_p D(p, p) * B_pp = 0, because each
-B_pp = 0. So Phi only "sees" off-diagonal entries.
-
-Now a "row-only" matrix H with H(p, q) = r_p (independent of q). Then
-
- Phi(H) = sum_{p, q} r_p * B_pq = sum_p r_p * (sum_q B_pq).
-
-So we need sum_q B_pq = 0 for every p. Look at the entry of B_pq indexed
-by ((a, b), (a', b')):
-
- B_pq[(a,b), (a',b')] = (x_p - x_q) w_p w_q x_p^{a+a'} x_q^{b+b'}.
+6. LINEAR ALGEBRA CRASH COURSE
-Sum over q, holding p, a, b, a', b' fixed:
+6.1 Vector spaces. A real vector space V has + and scalar multiplication,
+obeying the obvious rules. Examples: R^N and R^{a x b} (a-by-b real
+matrices).
- sum_q B_pq[(a,b),(a',b')]
- = w_p x_p^{a+a'} * [ x_p * sum_q w_q x_q^{b+b'}
- - sum_q w_q x_q^{1+b+b'} ].
+6.2 Subspaces. A SUBSPSACE U of V is a subset that contains 0 and is
+closed under + and scalar multiplication. If U and V are subspaces of
+W, so are U cap V = {w : w in U and w in V} and U + V = {u+v}.
-Both inner sums vanish by the barycentric identity 14.4: b + b' <=
-2s - 2 = n - 3 (below n-2) and 1 + b + b' <= 2s - 1 = n - 2. So the
-left side is zero. Same argument with p, q swapped handles "column-only"
-matrices H(p,q) = c_q: sum_p B_pq = 0. Therefore Phi(H) = 0 for any
-row-plus-column matrix H. Done.
+6.3 Independence, basis, dimension. A list v_1,...,v_k is INDEPENDENT
+if sum c_i v_i = 0 forces all c_i = 0. A BASIS is a spanning
+independent list. Its size is the DIMENSION (uniquely defined).
-16.7 Property (iii) verified: Phi(S_prec) is invertible. This is the
-core of the proof.
+6.4 Linear maps. T : V -> W is LINEAR if T(av + bw) = a T(v) + b T(w).
+The KERNEL ker T = {v : T(v) = 0} and IMAGE im T = {T(v) : v in V} are
+subspaces. Rank-nullity:
+ dim V = dim ker T + dim im T.
-Step A (natural order reduces to Phi(H)). Consider the natural order
-1 < 2 < ... < n. Define H(p, q) = 1 if p > q, 0 otherwise. Then
+6.5 Matrices. An a-by-b real matrix M acts on R^b by x -> Mx.
+ rank M = dim im M;
+ nullity M = dim ker M = b - rank M;
+ M square is INVERTIBLE iff rank M = b.
- S_nat = (1/2) 1 1^T - H - (1/2) I_n,
+Rank facts:
+ rank(A + B) <= rank A + rank B (subadditivity)
+ rank(A B) <= min(rank A, rank B) (submultiplicativity).
-where 1 = all-ones column (length n), I_n = identity. Check:
+6.6 Polynomials. A nonzero real polynomial of degree <= k has at most
+k distinct real roots. So if a polynomial of degree <= k vanishes at
+k+1 distinct reals, it is identically zero; and if two such polynomials
+agree at k+1 distinct reals, they are equal.
- p < q: 1/2 - 0 - 0 = 1/2. (correct)
- p > q: 1/2 - 1 - 0 = -1/2. (correct)
- p = q: 1/2 - 0 - 1/2 = 0. (correct)
-
-Apply Phi:
-
- Phi(S_nat) = (1/2) Phi(1 1^T) - Phi(H) - (1/2) Phi(I_n).
-
-Now Phi(1 1^T) = sum_{p,q} B_pq. But sum_q B_pq = 0 for each p, so
-Phi(1 1^T) = 0. And Phi(I_n) = sum_p B_pp = 0. Therefore
-
- Phi(S_nat) = -Phi(H).
-
-It remains to show Phi(H) is invertible.
-
-Step B (rewrite H). Define H'(p, q):
-
- For p <= s+1: H'(p, q) = H(p, q) (1 if p > q, 0 otherwise).
- For p > s+1: H'(p, q) = H(p, q) - 1 (so = 0 if p > q, -1 if p <= q).
-
-Then H(p, q) - H'(p, q) = 0 for p <= s+1 and = 1 for p > s+1. So it
-is a ROW-ONLY matrix (row p has constant value 0 or 1). Phi annihilates
-it by 16.6. Hence Phi(H) = Phi(H').
-
-Step C (read off Q_s). Compute H' on off-diagonal entries:
-
- p <= s+1, q < p: H'(p,q) = +1. (first triangle of Q_s)
- p <= s+1, q > p: H'(p,q) = 0.
- p > s+1, q < p: H'(p,q) = 0.
- p > s+1, q > p: H'(p,q) = -1. (second triangle of Q_s)
- diagonal: H'(p,p) = -1 or 0, but B_pp = 0 so ignored.
-
-So off the diagonal:
-
- Phi(H) = sum_{(p, q) in first triangle of Q_s} (+1) * B_pq
- + sum_{(p, q) in second triangle of Q_s} (-1) * B_pq.
-
-Write the sum instead over all (p, q) in Q_s using a sign (H') and the
-(x_p - x_q) factor inside B_pq:
-
- Phi(H) = sum_{(p, q) in Q_s} H'(p, q) * (x_p - x_q) w_p w_q *
- h_pq h_pq^T.
-
-Form the s^2-by-s^2 matrix A_Q with COLUMNS given by the vectors h_pq
-for (p, q) in Q_s (in any fixed order). Form the diagonal matrix
-
- D_Q = diag_{(p,q) in Q_s} ( H'(p,q) * (x_p - x_q) * w_p * w_q ).
+7. THE SUBSPACE INTERSECTION LEMMA
+7.1 Statement. Let W be a real vector space of dimension N, and let
+U_1,...,U_m and V_1,...,V_m be subspaces of W with
+ U_i cap V_i = {0} for every i.
Then
-
- Phi(H) = A_Q * D_Q * A_Q^T.
-
-Step D (invertibility). A_Q is invertible by Lemma 15.4 (two-triangle
-interpolation). D_Q is diagonal with all entries nonzero: H'(p,q) is
-= +1 or -1 on Q_s, x_p != x_q for p != q, and w_p, w_q are nonzero. So
-Phi(H) is invertible as a product of three invertible matrices. Hence
-Phi(S_nat) = -Phi(H) is invertible.
-
-Step E (arbitrary order). Let prec be ANY strict total order on
-{1, ..., n}. Choose pi in {1, ..., n}! with pi(1) prec pi(2) prec ...
-prec pi(n). Define a new node tuple
-
- x'_r = x_{pi(r)}, F'_r = F'(x_{pi(r)}), w'_r = w_{pi(r)}.
-
-Let Phi' be the SAME construction as 16.4, but built from the relabeled
-nodes x'_1, ..., x'_n instead of x_1, ..., x_n. By Step D applied to
-Phi', the matrix Phi'(S_nat) is invertible.
-
-Now relate Phi'(S_nat) to Phi(S_prec). For each r, w,
-
- B'_{rw} = (x'_r - x'_w) w'_r w'_w * h'_{rw} h'^T_{rw}
- = (x_{pi(r)} - x_{pi(w)}) w_{pi(r)} w_{pi(w)}
- * h_{pi(r), pi(w)} h^T_{pi(r), pi(w)}
- = B_{pi(r), pi(w)}.
-
-And S_nat(r, w) = +1/2 if r < w, -1/2 if r > w, 0 if r = w. Recalling
-the ordering pi(1) prec pi(2) prec ..., we see r < w iff pi(r) prec
-pi(w). So S_nat(r, w) = S_prec(pi(r), pi(w)) for all r, w.
-
-Therefore Phi'(S_nat) = sum_{r, w} S_nat(r, w) B'_{rw}
- = sum_{r, w} S_prec(pi(r), pi(w)) B_{pi(r), pi(w)}.
-
-Substitute p = pi(r), q = pi(w) (a bijection on {1,...,n}^2):
-
- Phi'(S_nat) = sum_{p, q} S_prec(p, q) B_pq = Phi(S_prec).
-
-Hence Phi(S_prec) = Phi'(S_nat) is invertible. Done with property (iii).
-
-16.8 Summary. The linear map Phi : R^{n x n} -> R^{s^2 x s^2} defined
-in 16.4 has all three required properties (i)-(iii). It is our "rank
-detector."
-
-16.9 What remains for the odd case. Given a minimum drawing D:
-
- - J^{ik} = n-by-n blocks of Section 10.7.
- - R_ik = Phi(J^{ik}).
- - X_i = R_i1 and Y_k = R_11 - R_1k, so R_ik = X_i - Y_k (Section 13.4).
- - X_i - Y_i = R_ii = Phi(J^{ii}) = Phi(S_prec of a_i), which is
- invertible by property (iii).
- - For i != k, rank R_ik <= c_ik, where c_ik is the number of
- crossing points between edges of star i and edges of star k.
-
-Combining with the rank-sum corollary (9.1), we get the lower bound.
-That is the content of Section 18.
+ sum_{i,j=1}^m dim(U_i cap V_j) <= floor(m^2/4) * N.
+
+7.2 Sharpness. Fix a direct-sum decomposition W = P + Q. Put
+(U_i, V_i) = (P, Q) for i in the first floor(m/2) indices and
+(Q, P) for the remaining ceil(m/2) indices. Every diagonal intersection
+is {0}, and the off-diagonal sum is
+ floor(m/2) ceil(m/2) * (dim P + dim Q)
+ = floor(m^2/4) * N,
+matching the bound. So the constant floor(m^2/4) is exact.
+
+7.3 Proof. Fix distinct real numbers t_1, ..., t_m ("nodes").
+
+For a subspace Z of W and an integer h >= 0, define
+ P_h(Z) = { sum_{e=0}^h z_e t^e : z_e in Z,
+ deg p <= h, p(t_i) in U_i for all i },
+ P_{-1}(Z) = {0},
+ k_h(Z) = dim P_h(Z) - dim P_{h-1}(Z),
+ E_h(Z;t) = { p(t) : p in P_h(Z) }.
+
+(Here Z[xi] means "polynomials with coefficients in Z"; the condition
+"p(t_i) in U_i" makes P_h(Z) a subspace.)
+
+Step 1 (evaluation away from nodes). For t not in {t_1,...,t_m}, the
+map ev_t : P_h(Z) -> Z, p |-> p(t), has kernel (xi - t) P_{h-1}(Z):
+division by xi - t is well-defined because t is a scalar and the
+constraint at t_i != t is preserved. Rank-nullity gives
+ dim E_h(Z; t) = k_h(Z) for every non-node t. [1]
+
+Step 2 (evaluation at all nodes). The map
+ P_{m-1}(Z) -> product_{i=1}^m (U_i cap Z),
+ p |-> (p(t_1), ..., p(t_m))
+is an isomorphism: injective because a degree <= m-1 vector polynomial
+vanishing at the m distinct nodes t_i is zero (apply 6.6 coordinate by
+coordinate), surjective because Lagrange interpolation
+ p(xi) = sum_i z_i * prod_{k != i} (xi - t_k)/(t_i - t_k)
+lands in Z[xi] and satisfies p(t_i) = z_i. Hence
+ sum_{h=0}^{m-1} k_h(Z) = sum_{i=1}^m dim(U_i cap Z). [2]
+
+Step 3 (degree filtration of W). Fix t* outside the node set. The
+subspaces
+ E_0(W;t*) <= E_1(W;t*) <= ... <= E_{m-1}(W;t*)
+are nested. Let ell_h = k_h(W) - k_{h-1}(W) >= 0. Choose polynomials
+p_{h,1},...,p_{h,ell_h} in P_h(W) whose values at t* enlarge a basis
+of E_{h-1}(W;t*) to a basis of E_h(W;t*). In fixed coordinates on W,
+let M_h(t) be the matrix whose columns are all chosen polynomials
+through stage h; it has r_h = k_h(W) columns. Choose an r_h-row
+square minor Delta_h(t) with Delta_h(t*) != 0. Every column introduced
+at stage e has degree <= e, so expanding the determinant:
+ deg Delta_h(t) <= sum_{e=0}^h e * ell_e. [3]
+(If r_h = 0, take Delta_h = 1.)
+
+Step 4 (rank loss at a node). For a node t_j, let pi_j : W -> W/V_j
+be the quotient map. For t not a node, the kernel of pi_j on E_h(W;t)
+contains E_h(V_j;t), so by [1],
+ dim pi_j(E_h(W;t)) <= k_h(W) - k_h(V_j).
+Pass to t = t_j: every polynomial minor larger than that bound
+vanishes at infinitely many nonnodes (hence is the zero polynomial),
+so the bound still holds at t_j. But E_h(W;t_j) <= U_j and pi_j is
+injective on U_j (since U_j cap V_j = {0}), so
+ dim E_h(W;t_j) <= k_h(W) - k_h(V_j). [4]
+
+Step 5 (divisibility). The chosen columns of M_h(t_j) land in E_h(W;t_j),
+and by [4] the square matrix defining Delta_h has nullity at least
+k_h(V_j) at t_j. A square polynomial matrix with nullity >= q at t_j
+has determinant divisible by (xi - t_j)^q: take q independent kernel
+vectors at t_j, extend to a constant invertible column change, and note
+that q transformed columns then vanish at t_j; each contributes a
+factor of xi - t_j, while the column change rescales the determinant by
+a nonzero constant. Applied at all m distinct nodes:
+ product_{j=1}^m (xi - t_j)^{k_h(V_j)} divides Delta_h(xi).
+Delta_h is nonzero (Delta_h(t*) != 0), so
+ sum_{j=1}^m k_h(V_j) <= deg Delta_h <= sum_{e=0}^h e * ell_e.
+ [5]
+
+Step 6 (assemble). Sum [5] over h = 0,...,m-1:
+ sum_{i,j} dim(U_i cap V_j)
+ = sum_{h=0}^{m-1} sum_j k_h(V_j) [by [2] with Z = V_j]
+ <= sum_{h=0}^{m-1} sum_{e=0}^h e * ell_e
+ = sum_{e=0}^{m-1} e (m - e) * ell_e
+ <= floor(m^2/4) * sum_{e=0}^{m-1} ell_e
+ = floor(m^2/4) * dim E_{m-1}(W; t*)
+ <= floor(m^2/4) * N. [by 6.6]
+
+8. RANK SUMS OF DIFFERENCES
+
+8.1 Corollary. Let X_1,...,X_m and Y_1,...,Y_m be d-by-d real matrices
+with X_i - Y_i invertible for every i. Then
+ sum_{i!=k} rank(X_i - Y_k) >= 2 d_m d,
+where d_m = floor(m/2) floor((m-1)/2) and the sum is over ORDERED pairs
+of distinct indices.
+
+8.2 Proof. Work in W = R^d + R^d (direct sum), dim W = 2d. Set
+ U_i = { (v, X_i v) : v in R^d },
+ V_j = { (v, Y_j v) : v in R^d }.
+Then
+ U_i cap V_j = { (v, X_i v) : v in ker(X_i - Y_j) },
+and the map v |-> (v, X_i v) identifies ker(X_i - Y_j) with U_i cap V_j,
+so
+ dim(U_i cap V_j) = d - rank(X_i - Y_j).
+For i = j, X_i - Y_i is invertible, so U_i cap V_i = {0}. Lemma 7.1
+with N = 2d gives
+ sum_{i,j} (d - rank(X_i - Y_j)) <= floor(m^2/4) * 2d,
+i.e., with S = sum_{i,j} rank(X_i - Y_j),
+ S >= d * (m^2 - 2 floor(m^2/4)).
+The m diagonal terms each equal d, so the off-diagonal sum satisfies
+ sum_{i!=k} rank(X_i - Y_k) = S - m d
+ >= d * (m^2 - m - 2 floor(m^2/4)).
+Direct expansion:
+ m = 2r: m^2 - m - 2 floor(m^2/4)
+ = 4r^2 - 2r - 2r^2 = 2r(r-1) = 2 d_m,
+ m = 2r+1: m^2 - m - 2 floor(m^2/4)
+ = (2r+1)^2 - (2r+1) - 2(r^2+r) = 2r^2 = 2 d_m.
+Hence the off-diagonal sum is at least 2 d_m d. [QED]
+
+8.3 A concrete check. Take m = 4, so d_m = floor(4/2) floor(3/2) = 2.
+For any 4 pairs of d-by-d matrices (X_i, Y_i) with X_i - Y_i invertible,
+the corollary guarantees
+ sum_{i != k} rank(X_i - Y_k) >= 2 d_m d = 4d,
+over the 12 off-diagonal ordered pairs. In the crossing application
+(Section 16) each rank(R_ik) is bounded by the crossing count c_ik of
+stars i and k, and sum_{i != k} c_ik = 2 c(D). The corollary gives
+ 4d <= 2 c(D), so c(D) >= 2d = d_4 d_n.
+This matches the odd-case theorem cr(K_{4,n}) = d_4 d_n.
==============================================================================
-PART VI THE FINISH
+PART V GEOMETRIC MACHINERY
==============================================================================
-17. ASSEMBLING THE LOWER BOUND
-------------------------------------------------------------------------------
-
-17.1 Where we are. Three ingredients are now assembled.
-
-GEOMETRY (Part IV).
- - Any drawing D of K_{m,n} produces an antisymmetric matrix J with
- n-by-n blocks J^{ik} (Section 10).
- - Cycle pairing (Lemma 12.2) makes every block-difference
- H(i,k) = J^{ik} - J^{i1} - J^{1k} + J^{11}
- into an ADDITIVE (row-plus-column) matrix.
-
-RANK DETECTOR (Part V).
- - A linear map Phi : R^{n x n} -> R^{s^2 x s^2} with three properties:
- (i) Phi(H) = 0 when H is additive;
- (ii) Phi(E_pq) has rank <= 1 for every standard matrix E_pq;
- (iii) Phi(S_prec) is invertible for every strict total order prec.
-
-RANK-SUM COROLLARY (Part III, Corollary 9.1).
- - If X_i - Y_i is invertible for every i in {1, ..., m}, then
- sum_{i != k} rank(X_i - Y_k) >= 2 d_m d,
- where d is the common size of the X_i and Y_k matrices (in our
- odd-n application, d = d_n = s^2).
-
-17.2 The three-step chain.
-
-Step 1 (from J to differences). Set R_ik = Phi(J^{ik}). Since Phi
-annihilates additive matrices, applying it to H(i,k) gives
-
- R_ik - R_i1 - R_1k + R_11 = 0,
-
-hence R_ik = R_i1 + R_1k - R_11. Define X_i = R_i1 and
-Y_k = R_11 - R_1k. Then
-
- R_ik = X_i - Y_k for all i, k.
-
-Step 2 (diagonal invertibility). When k = i, R_ii = Phi(J^{ii}). But
-J^{ii} = S_prec(a_i), the spoke-order matrix at vertex a_i, so property
-(iii) makes Phi(J^{ii}) invertible. Hence X_i - Y_i = R_ii is
-invertible for every i.
-
-Step 3 (rank bound). For i != k, rank(R_ik) <= c_{ik}, where c_{ik}
-is the number of crossing points between edges of star a_i and edges
-of star a_k. This is because each B_pq has rank <= 1 and only pairs
-ip, kq that actually cross contribute nonzero terms off the diagonal.
-
-17.3 The finish. Apply the rank-sum corollary to Steps 2 and 3:
-
- 2 d_m d_n <= sum_{i != k} rank(X_i - Y_k)
- = sum_{i != k} rank(R_ik)
- <= sum_{i != k} c_{ik}
- = 2 c(D).
-
-Here the last equality holds because each crossing of D is between two
-edges with distinct b-vertices (normalization), and is counted once in
-c_{ik} and once in c_{ki}. Therefore c(D) >= d_m d_n. That proves the
-odd case. Sections 18 and 19 do every check explicitly.
-
-17.4 The even case. Reduce to odd by deleting one b-vertex at a time
-and averaging (Section 19).
-
-18. THE ODD CASE
-------------------------------------------------------------------------------
-
-18.1 Setup. Let n = 2s+1 (odd, s >= 1) and m >= 3. Put d = d_n = s^2.
-Take an arbitrary minimum drawing D of K_{m,n}, normalized as in
-Lemma 20.1. This gives us the matrix J of Section 10, and its n-by-n
-blocks J^{ik} for 1 <= i, k <= m.
-
-18.2 The rank detector. Build the linear map Phi from Section 16, with
-output dimension s^2 = d_n. Set
-
- R_ik = Phi(J^{ik}) (an s^2-by-s^2 matrix)
- X_i = R_i1
- Y_k = R_11 - R_1k
-
-for all 1 <= i, k <= m.
-
-18.3 The difference form holds. By Section 13.4, we have
-
- R_ik = X_i - Y_k for all i, k.
-
-In particular, taking k = i:
-
- X_i - Y_i = R_ii = Phi(J^{ii}).
-
-18.4 Diagonal invertibility. By Section 10.7, J^{ii} is exactly the
-spoke-order matrix S_prec of vertex a_i. Property (iii) of Section 16
-says Phi(S_prec) is invertible. Hence
-
- X_i - Y_i is invertible for every i.
-
-This is the hypothesis of Corollary 9.1.
-
-18.5 Off-diagonal rank bound. Fix i != k. We claim
-
- rank(R_ik) <= c_{ik},
-
-where c_{ik} = number of crossing points between edges of the i-th star
-(all edges from a_i) and the k-th star (all edges from a_k).
-
-Proof. Write R_ik = sum_{p,q} J^{ik}(p,q) * B_pq. By property (ii),
-each B_pq has rank <= 1. By subadditivity of rank,
-
- rank(R_ik) <= #{ (p, q) with p != q and J^{ik}(p, q) != 0 }.
-
-Why "p != q"? Because B_pp = 0, so diagonal terms of J^{ik} contribute
-nothing to Phi(J^{ik}). The remaining entries J^{ik}(p, q) for p != q
-equal I(ip, kq) (the signed crossing count between edges a_i b_p and
-a_k b_q; no shared endpoint since i != k and p != q).
-
-For I(ip, kq) to be nonzero, the two edges must cross at least once.
-Each crossing point between edge ip and edge kq is a specific pair
-(p, q) with p != q. Therefore
-
- #{ (p,q) : p != q, I(ip, kq) != 0 } <= c_{ik}.
-
-So rank(R_ik) <= c_{ik}. Done.
-
-18.6 Apply the rank-sum corollary. Corollary 9.1, applied to the d-by-d
-matrices X_1, ..., X_m, Y_1, ..., Y_m, gives
-
- sum_{i != k} rank(X_i - Y_k) >= 2 d_m d = 2 d_m d_n.
-
-That is, sum_{i != k} rank(R_ik) >= 2 d_m d_n.
-
-Combining with 18.5:
-
- 2 d_m d_n <= sum_{i != k} rank(R_ik)
- <= sum_{i != k} c_{ik}
- = 2 c(D).
-
-The last equality: every crossing point of D is between two edges
-a_i b_p and a_k b_q with i != k (since adjacent edges never cross in
-the normalized drawing). Such a crossing is counted once in c_{ik} and
-once in c_{ki}, hence contributes exactly 2 to the double sum. Total:
-2 c(D). Therefore c(D) >= d_m d_n.
-
-18.7 Conclusion for odd n. Every minimum drawing D has c(D) >=
-d_m d_n. So cr(K_{m,n}) >= d_m d_n. Combined with the upper bound
-cr(K_{m,n}) <= d_m d_n (Section 4), we get equality.
-
-If m <= 2, then d_m = 0, and the upper bound gives cr(K_{m,n}) <= 0,
-hence = 0 = d_m d_n. So all m >= 1 are covered by the odd case.
-
-19. THE EVEN CASE
-------------------------------------------------------------------------------
-
-19.1 Setup. Let n > 2 be even and m >= 1. Write n = 2s.
-
-19.2 The key identity. We need
-
- n * d_{n-1} / (n - 2) = d_n.
-
-Direct verification. With n = 2s:
-
- d_{n-1} = d_{2s-1} = (s-1)^2
- d_n = d_{2s} = s(s-1)
-
-so n * d_{n-1} / (n - 2) = (2s)(s-1)^2 / (2(s-1)) = s(s-1) = d_n.
-
-19.3 The strategy (vertex deletion). Take a minimum drawing D of
-K_{m,n}, normalized. For each p in {1, ..., n}, let D_p be the
-sub-drawing obtained by deleting b_p and all n-1 edges incident to it.
-D_p is a drawing of K_{m,n-1} (with n-1 odd).
-
-Each c(D_p) is the count of crossings of D that do NOT involve an edge
-at b_p. So c(D_p) = c(D) - r_p where r_p is the count of crossings
-involving at least one edge at b_p.
-
-By the odd case (Section 18), c(D_p) >= d_m * d_{n-1}.
+9. SIGNED INTERSECTIONS
+
+9.1 Setting. Fix a minimum drawing D of K_{m,n}, normalized as in
+Section 18.
+
+9.2 Orient every edge a_i b_p FROM a_i TO b_p. Call this the fixed
+orientation.
+
+9.3 Signed crossing count. For oriented edges e,f, let I(e,f) be the
+sum over interior crossings x of e with f of
+ sign( det(u_x, v_x) ),
+where u_x and v_x are the tangents of e and f at x, both directed by
+the fixed orientation. Conventions:
+ I(e,e) = 0,
+ I(e,f) = -I(f,e).
+
+9.4 Spoke order at a vertex. At a vertex v, choose a "cut" between
+two consecutive edges leaving v, then list all edges at v counter-
+clockwise from that cut. Define
+ T_v(e,f) = +1 if e precedes f in that list,
+ -1 if f precedes e,
+ 0 if e = f,
+and
+ sigma_{v,e} = +1 if e is oriented OUT of v,
+ -1 if e is oriented INTO v.
+For the fixed orientations, sigma = +1 at every a_i and sigma = -1 at
+every b_p. Hence sigma_{v,e} sigma_{v,f} = +1 whenever e and f share
+the vertex v.
+
+9.5 The matrix J. For any two edges e,f of K_{m,n}, define
+ J(e,f) = I(e,f)
+ + (1/2) * sum over common endpoints v of e,f
+ sigma_{v,e} sigma_{v,f} T_v(e,f).
+Reading off the cases:
+ e = f: J(e,e) = 0.
+ share a_i only: J(e,f) = I(e,f) + (1/2) T_{a_i}(e,f).
+ share b_p only: J(e,f) = I(e,f) + (1/2) T_{b_p}(e,f).
+ share nothing: J(e,f) = I(e,f).
+Because I and T are antisymmetric, J is antisymmetric: J(e,f) = -J(f,e).
+
+9.6 Blocks. Number the edges as e_{ip} = a_i b_p. Define
+ J^{ik}(p,q) = J(e_{ip}, e_{kq}).
+Each J^{ik} is n x n; J is mn x mn, arranged in an m-by-m grid of
+n-by-n blocks.
+
+9.7 Diagonal blocks are spoke orders. For p != q,
+ J^{ii}(p,q) = I(e_{ip}, e_{iq}) + (1/2) T_{a_i}(e_{ip}, e_{iq}).
+The first term is zero (adjacent edges at a_i do not cross). So
+ J^{ii}(p,q) = (1/2) T_{a_i}(e_{ip}, e_{iq}).
+This is exactly HALF the comparison-sign matrix of the spoke order at
+a_i, i.e.,
+ J^{ii} = S_prec,
+ S_prec(p,q) = +1/2 if p precedes q,
+ -1/2 if q precedes p,
+ 0 if p = q.
+That is the S_prec whose invertibility the detector will need.
+
+10. THE CHORD FORMULA
+
+10.1 Two oriented chords of a disk. Let C and E be two oriented
+straight chords of a round disk with four distinct endpoints. Define
+endpoint coefficients
+ eps_C(u) = -1 if u = start(C),
+ +1 if u = end(C),
+ 0 otherwise,
+and similarly eps_E.
+
+10.2 The chord formula. Place a "cut" in the boundary circle away
+from all four endpoints. For two boundary points u, w, let T(u,w) be
++1 if u precedes w counterclockwise from the cut and -1 if w precedes
+u. Then the signed intersection of C and E equals
+ I(C,E) = (1/2) sum_{u in {start C, end C}}
+ sum_{w in {start E, end E}}
+ eps_C(u) eps_E(w) T(u,w).
+
+10.3 Cut invariance. Moving the cut past one boundary point x shifts
+every T-value by a step function whose change contributes a constant
+multiple of sum_w eps_E(w) = (-1) + (+1) = 0. Same when the cut passes
+an endpoint of E. So the right-hand side does not depend on the cut.
+
+10.4 Evaluate. Place the cut just before start(C). Then
+ - For u = start(C), T(start C, w) = +1 for both w. The
+ contribution is (1/2)(-1)(eps_E(start E) + eps_E(end E)) = 0.
+ - For u = end(C), T(end C, w) = -1 for w on the open CCW arc
+ from start(C) to end(C), and +1 for w on the complementary arc.
+ Let A be the sum of eps_E(w) over the first arc and B over the
+ complementary arc. Then A + B = 0 and the contribution is
+ (1/2)(+1)(-A + B) = -A.
+Hence
+ I(C,E) = - sum_{w on the open CCW arc from start C to end C}
+ eps_E(w).
+
+10.5 What the formula says.
+ Nonalternating: both endpoints of E lie on the same arc. The
+ sum over the arc is either eps_E + eps_E = 0 (both on) or 0
+ (both off), so I = 0.
+ Alternating: one endpoint on each arc. The sum picks up exactly
+ one eps_E value, giving +1 or -1 depending on orientation. This
+ matches the geometric sign of a transverse crossing.
+
+10.6 Why we need it. When a shared vertex disk is replaced by chords,
+the chord formula tells us the local contribution of the disk to a
+signed intersection. The factor 1/2 in J comes from averaging the two
+possible "shifts" of a track (left and right), as in Section 11.
+
+11. THE CYCLE-PAIRING LEMMA
+
+11.1 Cycle vectors. A CYCLE is a closed walk visiting no vertex
+twice except at its start. Given an oriented cycle of K_{m,n}, its
+CYCLE VECTOR z in R^{E(K_{m,n})} has
+ z_e = +1 if e is traversed with the fixed orientation,
+ -1 if against,
+ 0 if unused.
+
+11.2 Lemma (cycle pairing). For any two oriented simple cycles of
+K_{m,n} with cycle vectors z, y,
+ z^T J y = 0.
+
+11.3 Proof. Let the two cycles be C (using z) and D (using y).
+
+Step 1. Replace C by a closed polygonal walk gamma: place small round
+vertex disks centered at the vertices of C, all disjoint, meeting only
+the drawing's straight spokes; inside each disk replace the two
+incident spokes by the chord joining their boundary endpoints. Outside
+the disks keep the original tracks. gamma is a closed polygonal walk
+(possibly with self-intersections), carrying signed weights z.
+
+Step 2. Replace D by two nearby walks eta_+ (shifted left) and
+eta_- (shifted right) relative to the fixed orientation. Inside small
+disks centered at crossings and bends of D, connect the shifted ends by
+short arcs; choose shifts tiny enough that
+ (i) at each crossing disk, shifted tracks meet the corresponding
+ unshifted tracks with the same crossing sign as before;
+ (ii) at each shared vertex disk, the two shifted copies of a
+ common spoke's boundary endpoint lie on OPPOSITE sides of
+ the unshifted endpoint, so their T-signs cancel on average.
+Then eta_+ and eta_- are closed polygonal walks carrying weights y.
+
+Step 3. Two closed polygonal walks with only transverse intersections
+have total signed intersection zero. Reason: pick a point o outside
+everything, cone the first walk to o, and note each triangle [o, u, w]
+bounds a region, so every entrance of the second walk to that region is
+matched by an exit with the opposite sign - the total is zero. Summing
+over all triangle boundaries, the extra cone segments [o,u] cancel in
+pairs, leaving exactly the first walk. The argument counts oriented
+traversals and so works for non-simple walks. Hence signed intersection
+of gamma with eta_+ equals zero, and likewise for eta_-.
+
+Step 4. For either eta, the signed intersection of gamma with eta
+splits into contributions:
+ exterior part + vertex-disk parts = 0.
+The exterior part is the sum over pairs of edges (each from a cycle) of
+z_e y_f I(e,f), equal to z^T I y; it does not depend on the choice of
+shift. At a shared vertex v, the local contribution is
+ (1/2) sum_{e,f at v} sigma_{v,e} sigma_{v,f} T_v(e,f) z_e y_f,
+the 1/2 being the average of the two shifts. When e = f, the two
+shifted endpoints sit on opposite sides of the unshifted endpoint, so
+their T-signs are opposite and average to zero, matching the convention
+T_v(e,e) = 0.
+Summing:
+ 0 = z^T I y + (1/2) sum_v sum_{e,f at v}
+ sigma sigma T z_e y_f
+ = z^T J y. [QED]
+
+11.4 The 1/2 in the definition of J is exactly what averaging over
+left and right shifts produces; the antisymmetric convention
+T_v(e,e) = 0 forces the two shifts to cancel at diagonal spokes.
+
+12. THE ADDITIVE BLOCK RELATION
+
+12.1 Additive matrices. A matrix H in R^{n x n} is ADDITIVE (row
+plus column) if there exist vectors r, c with H(p,q) = r_p + c_q for
+all p, q. Equivalently, for all p, p', q, q':
+ H(p,q) - H(p,q') - H(p',q) + H(p',q') = 0.
+Proof: (=>) immediate expansion. (<=) fix p_0 = q_0 = 1 and set
+r_p = H(p,1) and c_q = H(1,q) - H(1,1).
+
+12.2 Lemma (additive block relation). For all 1 <= i,k <= m, the
+n x n matrix
+ H(i,k) = J^{ik} - J^{i1} - J^{1k} + J^{11}
+is additive.
-19.4 Count crossings per p. Every crossing of D is between two edges
-a_i b_p and a_k b_q with p != q (adjacency normalization says edges
-at the same b-vertex never cross). Such a crossing:
+12.3 Proof. Fix i,k. If i = 1 then H(1,k) = 0, additive. Same if
+k = 1. Assume i,k >= 2. If p = p' or q = q', the alternating sum
+vanishes trivially. Assume p != p' and q != q'.
+
+Build the 4-cycle z on {ip, 1p, 1p', ip'}:
+ cycle: a_i -> b_p -> a_1 -> b_p' -> a_i.
+Traversals vs fixed orientations:
+ ip: a_i -> b_p, matches; z_{ip} = +1
+ 1p: b_p -> a_1, against a_1 -> b_p; z_{1p} = -1
+ 1p': a_1 -> b_p', matches; z_{1p'} = +1
+ ip': b_p' -> a_i, against a_i -> b_p'; z_{ip'} = -1
+ z = 0 elsewhere.
+
+Similarly the 4-cycle y on {kq, 1q, 1q', kq'} gives
+ y_{kq} = +1, y_{1q} = -1, y_{1q'} = +1, y_{kq'} = -1,
+ y = 0 elsewhere.
+
+By Lemma 11.2, z^T J y = 0. Expanding all 16 nonzero products and
+regrouping:
+ z^T J y
+ = J(ip,kq) - J(ip,1q) - J(ip,kq') + J(ip,1q')
+ - J(1p,kq) + J(1p,1q) + J(1p,kq') - J(1p,1q')
+ + J(1p',kq) - J(1p',1q) - J(1p',kq') + J(1p',1q')
+ - J(ip',kq) + J(ip',1q) + J(ip',kq') - J(ip',1q')
+ = H(p,q) - H(p,q') - H(p',q) + H(p',q').
+Therefore H satisfies the characterizing four-term identity of 12.1,
+so H is additive. [QED]
+
+12.4 Consequence (differences form). Let Phi be ANY linear map on
+n x n matrices that annihilates every additive matrix. Applying Phi
+to 12.2:
+ Phi(J^{ik}) - Phi(J^{i1}) - Phi(J^{1k}) + Phi(J^{11}) = 0,
+i.e., with
+ R_ik = Phi(J^{ik}), X_i = R_i1, Y_k = R_11 - R_1k,
+for all i,k:
+ R_ik = X_i - Y_k.
+In particular for i = k,
+ X_i - Y_i = R_ii = Phi(J^{ii}) = Phi(S_prec at a_i).
+
+12.5 Goals for the detector Phi. For odd n = 2s+1 and d = s^2, we
+need a linear map Phi : R^{n x n} -> R^{d x d} with:
+ (i) Phi annihilates every additive matrix and every diagonal
+ matrix.
+ (ii) Phi(E_pq) has rank <= 1 for every standard matrix E_pq.
+ (iii) Phi(S_prec) is invertible for every strict total order prec
+ on {1,...,n}.
+Goals (i)-(ii) turn the block relations into a rank bound; goal (iii)
+gives the diagonal invertibility that the rank-sum corollary needs.
+Sections 13-15 build such a Phi.
- - contributes to r_p (crossing at b_p) and r_q (crossing at b_q);
- - is counted in c(D_{p'}) for every p' != p, p', i.e., for n-2
- values of p'.
+==============================================================================
+PART VI THE RANK DETECTOR
+==============================================================================
+13. LAGRANGE INTERPOLATION AND BARYCENTRIC WEIGHTS
+
+13.1 Lagrange. Given n distinct reals x_1,...,x_n and arbitrary
+values y_1,...,y_n, there is a unique polynomial P of degree <= n-1
+with P(x_i) = y_i. It is
+ P(t) = sum_{i=1}^n y_i L_i(t),
+ L_i(t) = prod_{k != i} (t - x_k) / (x_i - x_k).
+
+13.2 Barycentric form. Let F(t) = prod_{p=1}^n (t - x_p). Then
+F'(x_i) = prod_{k != i} (x_i - x_k), so
+ L_i(t) = F(t) / ((t - x_i) F'(x_i)).
+The numbers w_i = 1 / F'(x_i) are the BARYCENTRIC WEIGHTS. They are
+nonzero because the nodes x_i are distinct.
+
+13.3 Vanishing identity. If deg A <= n-2, then
+ sum_{i=1}^n A(x_i) * w_i = 0.
+Proof: By Lagrange, A(t) = sum_i A(x_i) L_i(t) as polynomials. Each
+L_i has leading coefficient w_i. The coefficient of t^{n-1} on the
+left side is 0 (since deg A <= n-2 < n-1); on the right it is
+sum_i A(x_i) w_i. Comparing gives the claim.
+
+14. TWO-TRIANGLE INTERPOLATION
+
+14.1 Setting. Fix n = 2s+1 distinct reals x_1,...,x_n. Consider
+bivariate polynomials P(u,v) of BIDEGREE <= (s-1, s-1) (i.e., deg_u <=
+s-1 and deg_v <= s-1). They form a real vector space of dimension
+s^2 = d, with monomial basis
+ { u^a v^b : 0 <= a, b <= s-1 }.
+For each pair (p,q), define the evaluation vector h_pq in R^{s^2} by
+ h_pq(a,b) = x_p^a * x_q^b ,
+so that P(x_p,x_q) = "c . h_pq" where c is the coefficient vector.
+
+14.2 The two-triangle pattern.
+ Q_s = { (p,q) : 1 <= q < p <= s+1 }
+ u { (p,q) : s+1 < p < q <= 2s+1 }.
+Its size:
+ |Q_s| = s(s+1)/2 + s(s-1)/2 = s^2 = d.
+For s=3 (n=7), with rows p and columns q, X = in Q_s:
+ p\q 1 2 3 4 5 6 7
+ 1 . . . . . . .
+ 2 X . . . . . .
+ 3 X X . . . . .
+ 4 X X X . . . .
+ 5 . . . . . X X
+ 6 . . . . . . X
+ 7 . . . . . . .
+Row 4 (= s+1) is the last row of the first (lower-left) triangle; it
+is exactly the row eliminated in Step A below. Column 1 is the
+corresponding column eliminated in Step B.
+
+14.3 Lemma (two-triangle interpolation). If P has bidegree <= (s-1,s-1)
+and vanishes at every (x_p, x_q) with (p,q) in Q_s, then P is the zero
+polynomial. Equivalently, { h_pq : (p,q) in Q_s } is a basis of R^{s^2}.
+
+14.4 Proof. Both sides have dimension s^2, so it suffices to prove
+injectivity. Induction on s.
+
+Base case, s=1: P is constant, Q_1 = {(2,1)}, so P(x_2,x_1) = 0 gives
+P = 0.
+
+Induction step (s >= 2).
+
+Step A: eliminate u - x_{s+1}. The points (s+1, 1), (s+1, 2), ...,
+(s+1, s) all lie in Q_s (q < p = s+1, so q <= s). Hence
+P(x_{s+1}, x_q) = 0 for q = 1,...,s. The polynomial P(x_{s+1}, v) has
+degree <= s-1 in v and s distinct roots, so it is identically zero.
+Hence
+ P(u,v) = (u - x_{s+1}) * P_1(u,v),
+ deg_u P_1 <= s-2, deg_v P_1 <= s-1.
+
+Step B: eliminate v - x_1. The points (p, 1) for p = 2,...,s all lie
+in Q_s (1 < p <= s < s+1). So P(x_p, x_1) = 0 for p = 2,...,s. Since
+x_p != x_{s+1} for p <= s, the factor (x_p - x_{s+1}) is nonzero, so
+P_1(x_p, x_1) = 0 for p = 2,...,s. The polynomial P_1(u, x_1) has
+degree <= s-2 in u and s-1 distinct roots, so it is identically zero.
+Hence
+ P_1(u,v) = (v - x_1) * R(u,v),
+ deg_u R <= s-2, deg_v R <= s-2,
+and
+ P(u,v) = (u - x_{s+1}) (v - x_1) R(u,v).
+
+Step C: what remains of Q_s. Columns and rows already used:
+ - step A used every point with p = s+1;
+ - step B used every point with q = 1.
+What is left of Q_s:
+ A = { (p,q) : 2 <= q < p <= s }
+ B = { (p,q) : s+1 < p < q <= 2s+1 }.
+At every point in A u B both factors (x_p - x_{s+1}) and (x_q - x_1)
+are nonzero, so R vanishes at all (x_p, x_q) with (p,q) in A u B.
+
+Step D: smaller Q_{s-1}. Define a tuple of 2s-1 distinct nodes
+ (y_1, ..., y_{2s-1})
+ = (x_{s+2}, x_{s+3}, ..., x_{2s+1}, x_2, x_3, ..., x_s),
+i.e., y_r = x_{s+1+r} for r = 1,...,s and y_r = x_{r-s+1} for
+r = s+1,...,2s-1. (This is exactly x_1,...,x_{2s+1} with x_1 and
+x_{s+1} removed.) Define S(u,v) = R(v,u). Then S has bidegree
+<= (s-2, s-2) = ((s-1)-1, (s-1)-1). We claim S vanishes on Q_{s-1} for
+the y-tuple.
+
+Case 1 (first triangle of Q_{s-1}): 1 <= w < r <= s.
+ y_r = x_{s+1+r}, y_w = x_{s+1+w},
+ S(y_r, y_w) = R(y_w, y_r) = R(x_{s+1+w}, x_{s+1+r}).
+Row index s+1+w, column index s+1+r. Since 1 <= w < r <= s,
+ s+1 < s+1+w < s+1+r <= 2s+1,
+so (s+1+w, s+1+r) lies in B, where R vanishes.
+
+Case 2 (second triangle of Q_{s-1}): s < r < w <= 2s-1.
+ y_r = x_{r-s+1}, y_w = x_{w-s+1},
+ S(y_r, y_w) = R(y_w, y_r) = R(x_{w-s+1}, x_{r-s+1}).
+Row index w-s+1, column index r-s+1. Since r < w and r >= s+1,
+ 2 <= r-s+1 < w-s+1 <= s,
+so (w-s+1, r-s+1) lies in A, where R vanishes.
+
+By induction, S = 0. Then R = 0, then P = 0. [QED]
+
+15. THE RANK DETECTOR
+
+15.1 Goal. For odd n = 2s+1, build Phi : R^{n x n} -> R^{s^2 x s^2}
+satisfying (i)-(iii) of Section 12.5.
+
+15.2 Setup. Fix nodes x_1 < x_2 < ... < x_n. Let
+F(t) = prod_p(t - x_p), w_p = 1 / F'(x_p).
+
+15.3 Blocks. For each (p,q) in {1,...,n}^2, recall h_pq from 14.1 and
+set
+ B_pq = (x_p - x_q) * w_p * w_q * (h_pq h_pq^T),
+where h_pq h_pq^T is the OUTER PRODUCT with entries
+ (h_pq h_pq^T)[(a,b), (a',b')] = x_p^{a+a'} * x_q^{b+b'}.
+
+15.4 Definition. Define Phi by
+ Phi(H) = sum_{p,q=1}^n H(p,q) * B_pq.
+Phi is linear in H, by construction.
+
+15.5 Property (ii). Phi(E_pq) = B_pq. Since h_pq != 0 (its (0,0)
+coordinate is 1) and (x_p - x_q) w_p w_q is a nonzero scalar when
+p != q, B_pq has rank exactly 1 for p != q, and B_pp = 0 (the
+prefactor x_p - x_p vanishes).
+
+15.6 Property (i). Phi(I_n) = sum_p B_pp = 0, so Phi annihilates
+every diagonal matrix. For a row-constant matrix H(p,q) = r_p,
+ Phi(H) = sum_p r_p * (sum_q B_pq).
+The (a,b; a',b') entry of sum_q B_pq is
+ sum_q (x_p - x_q) w_p w_q x_p^{a+a'} x_q^{b+b'}
+ = w_p x_p^{a+a'} * [ x_p * sum_q w_q x_q^{b+b'}
+ - sum_q w_q x_q^{1+b+b'} ].
+Since b + b' <= 2s-2 = n-3 < n-2 and 1 + b + b' <= 2s-1 = n-2, both
+inner sums vanish by the vanishing identity 13.3. So sum_q B_pq = 0
+for each p, and Phi annihilates row-constant matrices. Symmetrically,
+sum_p B_pq = 0 for each q, so Phi annihilates column-constant matrices.
+Any additive matrix is row-constant plus column-constant; hence
+Phi(H) = 0. This proves (i).
+
+15.7 Property (iii). Fix the natural order 1 < 2 < ... < n. Let
+H(p,q) = 1 if q < p, else 0. Then
+ S_nat = (1/2) 1 1^T - H - (1/2) I_n,
+where 1 = all-ones column. Check:
+ p < q: 1/2 - 0 - 0 = 1/2.
+ p > q: 1/2 - 1 - 0 = -1/2.
+ p = q: 1/2 - 0 - 1/2 = 0.
+Applying Phi and using (i):
+ Phi(S_nat) = (1/2) Phi(1 1^T) - Phi(H) - (1/2) Phi(I_n)
+ = -Phi(H).
+
+Step A. Define H' by
+ H'(p,q) = H(p,q) for p <= s+1,
+ = H(p,q) - 1 for p > s+1.
+Then H - H' is row-constant (value 0 for p <= s+1, 1 for p > s+1), so
+by (i) Phi(H) = Phi(H').
+
+Step B. Off the diagonal, H' equals
+ +1 on Q_s-first-triangle { q < p <= s+1 },
+ 0 elsewhere above the diagonal in rows p <= s+1,
+ 0 below the diagonal in rows p > s+1,
+ -1 on Q_s-second-triangle { s+1 < p < q }.
+On the diagonal H' may be nonzero; Phi kills B_pp = 0, so the diagonal
+does not contribute. So the off-diagonal support of H' is exactly Q_s,
+with sign +1 on the first triangle and -1 on the second.
+
+Step C. Group the Q_s pairs in any order, and let A_Q be the s^2 x s^2
+matrix whose columns are h_pq for (p,q) in Q_s. Let D_Q be the
+diagonal matrix
+ D_Q[(p,q),(p,q)] = H'(p,q) (x_p - x_q) w_p w_q
+for (p,q) in Q_s. Then
+ Phi(H') = A_Q * D_Q * A_Q^T.
+
+Step D. A_Q is invertible by Lemma 14.3, and every diagonal entry of
+D_Q is nonzero: H'(p,q) = +-1 on Q_s, x_p != x_q, w_p and w_q nonzero.
+Hence Phi(H') is invertible, and so is Phi(S_nat) = -Phi(H').
+
+Step E (arbitrary order). Let prec be any strict total order on
+{1,...,n}. Choose a bijection pi with pi(1) prec pi(2) prec ...
+prec pi(n). Build Phi' with nodes x'_r = x_{pi(r)}. Step D applies to
+Phi', so Phi'(S_nat) is invertible. Since
+ B'_{rw} = (x'_r - x'_w) w'_r w'_w h'_{rw} h'^T_{rw}
+ = B_{pi(r), pi(w)},
+and since r < w iff pi(r) prec pi(w), we have
+ S_nat(r,w) = S_prec(pi(r), pi(w)) for all r,w.
Therefore
+ Phi'(S_nat) = sum_{r,w} S_nat(r,w) B'_{rw}
+ = sum_{r,w} S_prec(pi(r),pi(w)) B_{pi(r),pi(w)}
+ = sum_{p,q} S_prec(p,q) B_{pq}
+ = Phi(S_prec).
+Hence Phi(S_prec) = Phi'(S_nat) is invertible.
- sum_{p=1}^{n} c(D_p) = (n - 2) * c(D).
-
-19.5 Combine. Summing the odd-case bound over p = 1, ..., n:
-
- sum_{p=1}^{n} c(D_p) >= n * d_m * d_{n-1}.
-
-Combining with 19.4:
-
- (n - 2) c(D) >= n * d_m * d_{n-1}.
-
-Divide by (n - 2) and apply 19.2:
-
- c(D) >= n * d_m * d_{n-1} / (n - 2) = d_m * d_n.
-
-19.6 Conclusion for even n. Every minimum drawing D has c(D) >=
-d_m d_n. Combined with the upper bound, cr(K_{m,n}) = d_m d_n.
-
-19.7 Sanity check. n = 4 (so s = 2, d_4 = 2). Bound becomes c(D) >=
-d_m * 2. Upper bound gives cr(K_{m,4}) <= d_m * 2. So equality.
-Matches cr(K_4,4) = 4 = d_4 * d_4 (m = 4 case).
+This completes the construction. The map Phi : R^{n x n} -> R^{s^2 x s^2}
+satisfies properties (i)-(iii) of Section 12.5.
-20. CLEANING UP A DRAWING (APPENDIX)
-------------------------------------------------------------------------------
-
-20.1 Lemma (Drawing normalization). An admissible continuous-arc
-drawing of a finite simple graph can be replaced by a polygonal drawing
-with:
-
- (a) at most the same number of crossings,
- (b) edges straight near every vertex and every crossing,
- (c) NO crossings between edges sharing an endpoint.
-
-20.2 Construction (sketch, from the original paper).
-
-Step 1: isolating the marked passages. Mark every vertex and every
-crossing of the given drawing. There are finitely many marks. Around
-each mark, insert a small closed round disk so that every edge visit
-to the disk corresponds to the intended local passage, and nonincident
-edges avoid the disk. This is possible since there are finitely many
-marks and edges are continuous arcs.
-
-Step 2: straightening the exterior pieces. Outside the disks, the
-drawing reduces to finitely many pairwise disjoint compact arcs. These
-admit pairwise disjoint open neighborhoods. A standard topological
-fact: any continuous path with compact image in an open subset of the
-plane can be replaced by a polygonal arc with the same endpoints, still
-inside that open set. So each exterior arc becomes polygonal.
-
-Step 3: filling the disks with straight chords or spokes. In each
-crossing disk, connect the two pairs of boundary endpoints by straight
-chords. They meet at most once (a straight line meets a circle in at
-most two points, so two chords cannot overlap or cross more than once);
-any meeting is an interior transverse crossing. In each vertex disk,
-choose a new vertex point off the finitely many lines through pairs of
-boundary endpoints, and join all boundary endpoints to it with straight
-spokes (spokes only meet at the vertex).
-
-Step 4: removing adjacent-edge crossings. Suppose two edges e = v u
-and f = v w share vertex v and still cross at some point x. Choose a
-small round disk around x containing only the two straight crossing
-strands. Swap the parts of e and f from v up to this disk, then join
-the swapped prefixes to the original suffixes. Inside the disk, use
-two disjoint chords pairing adjacent boundary points; the crossing at
-x disappears, and no new crossing is created (outside the disk
-everything is as before, inside the disk the two chords don't cross).
+==============================================================================
+PART VII THE ODD CASE
+==============================================================================
-The result may be two POLYGONAL WALKS (not paths), with possible
-self-intersections. Subdivide the walks at all remaining intersections
-and delete closed subwalks starting and ending at the same point; this
-yields simple polygonal edges. Direct inspection shows no new
-crossings are created and admissibility is preserved.
-
-Repeat Step 4 while an adjacent-edge crossing remains. Each step
-decreases the crossing count by at least 1, so this terminates. The
-final drawing is polygonal, straight near every vertex and crossing,
-has no adjacent-edge crossings, and no more crossings than the
-original. Done.
-
-20.3 Consequence. Starting from ANY minimum drawing, normalization
-gives a normalized minimum drawing with the same crossing count. All
-arguments in Parts IV-VI assume normalized drawings; we now know we
-can do so freely.
-
-21. WHERE TO LEARN MORE
-------------------------------------------------------------------------------
-
-21.1 Background on crossing numbers.
-
- - Pach and Toth, "Which crossing number is it anyway?", JCTB 2000.
- Explains the many conventions (point-count vs pair-count vs
- parity-based) for "the number of crossings". This document uses
- point-count throughout.
-
- - Erdos and Guy, "Crossing number problems", Amer. Math. Monthly,
- 1973. The historical survey of the Zarankiewicz problem.
-
-21.2 Historical progress on this exact problem.
-
- - Turan, "A note of welcome", J. Graph Theory 1977. The brick-factory
- origin of the problem.
-
- - Zarankiewicz, Fund. Math. 1955. The upper-bound construction and
- the (gapped) claim of optimality.
-
- - Kleitman, "The crossing number of K_{5, n}", JCT 1970. Exact values
- for small m, and the standard "vertex-deletion" argument used in
- Section 19.
-
- - Woodall, "Cyclic-order graphs and Zarankiewicz's conjecture",
- J. Graph Theory 1993. Verified K_{7,7} = 81 by computer search.
-
- - de Klerk, Maharry, Pasechnik, Richter, Salazar (2006) and
- Brosch-Polak (2024). Semidefinite-programming lower bounds
-
- - Balogh, Lidicky, Norin, Pfender, Salazar, Spiro (2023). Flag-algebra
- lower bound cr(K_{n,n}) >= 0.9118 d_n^2 + o(n^4) - the best previous
- bound.
-
-21.3 The specific tools used here.
-
- - Section 8: the "subspace intersection lemma". Related to
- Guruswami-Kopparty, "Explicit subspace designs", Combinatorica
- 2016 (determinant-multiplicity techniques).
-
- - Section 9: rank of differences. Consequence of Section 8 by
- "graph of a linear map" translation.
-
- - Section 12: cycle pairing. The zero of the total signed
- intersection of two closed plane curves.
-
- - Sections 14-16: Lagrange interpolation and the two-triangle
- pattern. Barycentric weights are from Berrut and Trefethen,
- "Barycentric Lagrange Interpolation", SIAM Review 2004.
-
- - Section 16: the rank detector construction. The key geometric fact
- is that the two-triangle set Q_s and the barycentric identity
- together make Phi(S_prec) invertible.
-
-21.4 A one-page diagram of the whole proof. The logical flow:
-
- A drawing D of K_{m,n}
- |
- | (normalize, Section 20)
- v
- Normalized minimum drawing D
- |
- | (build J, Sections 10-13)
- v
- Antisymmetric matrix J = [J^{ik}]_{i,k}, mn x mn
- |
- | (apply Phi, Sections 14-16)
- v
- Matrices R_ik, X_i, Y_k with R_ik = X_i - Y_k,
- X_i - Y_i invertible (spoke-order invertibility),
- rank R_ik <= c_ik (rank-leq-1 detector).
- |
- | (apply rank-sum corollary, Section 9)
- v
- 2 d_m d_n <= sum_{i != k} rank(R_ik) <= sum_{i != k} c_ik = 2 c(D)
- |
- v
- d_m d_n <= c(D).
-
- To handle even n: delete one b-vertex at a time, apply the odd case
- to the K_{m,n-1} sub-drawing, and average (Section 19).
-
-21.5 On the original source. This document is the "v2" rewrite of the
-research paper stored as crossing_number_bipartite_original.txt in the
-same repository (LaTeX source). It is written for high-school readers:
-every definition is given, every lemma is stated and proved (or, for
-the drawing-normalization lemma, at least sketched in full enough
-detail to be followable), and every tool is placed in context. No step
-of the argument is skipped, and no advanced background is assumed
-beyond the linear-algebra crash course in Section 7.
+16. THE ODD CASE OF THE LOWER BOUND
+
+16.1 Setup. Let n = 2s+1 >= 3, so d_n = s^2 =: d. Let m >= 3 (else
+d_m = 0 and the bound is trivial). Take a minimum drawing D of
+K_{m,n}, normalized as in Section 18. Build the block matrix J
+(Section 9). Use the detector Phi from Section 15, so Phi maps n x n
+matrices to s^2 x s^2 = d x d matrices.
+
+16.2 Definitions.
+ R_ik = Phi(J^{ik}) (a d x d matrix),
+ X_i = R_i1,
+ Y_k = R_11 - R_1k.
+
+16.3 Difference form. By 12.4 (additivity of H(i,k) and annihilation
+by Phi):
+ R_ik = X_i - Y_k for all 1 <= i, k <= m.
+
+16.4 Diagonal invertibility. Taking k = i:
+ X_i - Y_i = R_ii = Phi(J^{ii}) = Phi(S_prec of a_i).
+By 15.7 (property (iii)), Phi(S_prec) is invertible for every strict
+total order. Hence X_i - Y_i is invertible for every i.
+
+16.5 Off-diagonal rank bound. For i != k,
+ rank R_ik <= c_ik,
+where c_ik is the number of crossing POINTS between edges of the i-th
+and k-th stars.
+
+Proof. R_ik = sum_{p,q} J^{ik}(p,q) B_pq. Each B_pq has rank <= 1 (by
+15.5), so by subadditivity of rank,
+ rank R_ik <= #{ (p,q) : p != q, J^{ik}(p,q) != 0 }.
+(B_pp = 0 kills the diagonal entries.) For i != k, the entries at
+p != q are J^{ik}(p,q) = I(e_{ip}, e_{kq}) (edges with distinct
+endpoints). Any nonzero I-value requires at least one crossing of
+e_{ip} with e_{kq}, and each crossing point contributes to exactly one
+(p,q). So the count is at most c_ik.
+
+16.6 Apply rank-sum corollary. Section 8, applied to the matrices
+X_1,...,X_m, Y_1,...,Y_m (all d x d, with X_i - Y_i invertible by
+16.4), gives
+ sum_{i != k} rank(X_i - Y_k) >= 2 d_m d = 2 d_m d_n.
+Combining with 16.5:
+ 2 d_m d_n <= sum_{i != k} rank(R_ik)
+ <= sum_{i != k} c_ik
+ = 2 c(D).
+The final equality: every crossing of D joins edges with distinct
+b-endpoints (adjacency normalization), so it is counted exactly once in
+c_ik and exactly once in c_ki. Hence the double sum is 2 c(D).
+
+16.7 Conclusion. c(D) >= d_m d_n. Since D was an arbitrary minimum
+drawing, cr(K_{m,n}) >= d_m d_n. Together with the upper bound
+cr(K_{m,n}) <= d_m d_n:
+ cr(K_{m,n}) = d_m d_n for odd n >= 3.
+For m <= 2 the upper bound already gives cr = 0 = d_m d_n.
==============================================================================
-CLOSING: THE THEOREM, RESTATED
+PART VIII THE EVEN CASE
==============================================================================
-For all positive integers m, n:
+17. THE EVEN CASE
+
+17.1 Identity. For n = 2s >= 4,
+ n d_{n-1} / (n-2) = d_n.
+Check: d_{n-1} = d_{2s-1} = (s-1)^2, d_n = d_{2s} = s(s-1). Then
+ (2s)(s-1)^2 / (2s-2) = s(s-1) = d_n.
+
+17.2 Vertex deletion. Let n = 2s >= 4. Take a minimum drawing D of
+K_{m,n}, normalized. For each p = 1,...,n let D_p be D with the vertex
+b_p and its m incident edges deleted. D_p is a drawing of K_{m,n-1}
+(n-1 odd). By the odd case,
+ c(D_p) >= d_m d_{n-1} for every p.
+
+17.3 Double count. A crossing of D lies between two edges e_{ip} and
+e_{kq} with i != k and p != q (adjacency normalization). It involves
+exactly two b-vertices, b_p and b_q, so it survives in D_{p'} iff
+p' not in {p,q}: there are n-2 such p'. Therefore
+ sum_{p=1}^n c(D_p) = (n-2) c(D).
+
+17.4 Combine.
+ (n-2) c(D) = sum_p c(D_p) >= n d_m d_{n-1} = (n-2) d_m d_n,
+using 17.1 in the last step. Divide by n-2:
+ c(D) >= d_m d_n.
+Combined with the upper bound:
+ cr(K_{m,n}) = d_m d_n for every even n >= 4.
+Edge cases n <= 2 or m <= 2: the upper bound gives cr = 0 = d_m d_n.
- cr(K_{m,n}) = floor(m/2) * floor((m-1)/2) * floor(n/2) * floor((n-1)/2).
-
-That is the Zarankiewicz crossing-number formula, proven completely in
-this document.
+==============================================================================
+PART IX NORMALIZING A DRAWING
+==============================================================================
-Sanity checks:
- m = n = 3: 1 * 1 * 1 * 1 = 1.
- m = n = 4: 2 * 1 * 2 * 1 = 4.
- m = n = 5: 2 * 2 * 2 * 2 = 16.
- m = n = 6: 3 * 2 * 3 * 2 = 36.
- m = n = 7: 3 * 3 * 3 * 3 = 81.
- m = n = 8: 4 * 3 * 4 * 3 = 144.
+18. DRAWING NORMALIZATION
+
+18.1 Lemma. Every admissible continuous-arc drawing of a finite simple
+graph can be replaced by a polygonal drawing with
+ (a) at most the same number of crossing points,
+ (b) edges straight near every vertex and every crossing,
+ (c) no crossings between edges sharing an endpoint,
+ (d) no triple crossings, tangencies, or shared arcs.
+
+All arguments in Parts V-VII assume such a normalized drawing.
+
+18.2 Proof. Call the vertices and crossings of the drawing its MARKS
+(finitely many). Parameterize each edge e as a continuous injective
+arc gamma_e : [0,1] -> R^2.
+
+Step 1 (isolate marks). On each edge, choose pairwise disjoint
+parameter neighborhoods of its marked parameters (one-sided at 0 and
+1). For each mark w and edge e: the image of the compact parameter set
+outside its w-neighborhood is at positive distance from w (because it
+avoids w); an edge not incident to w has its whole compact image at
+positive distance from w. Since there are finitely many (e,w), there
+exist pairwise disjoint closed round disks D_w, centered at the marks,
+such that
+ - every visit of any edge to D_w lies in its w-neighborhood;
+ - every edge not incident to w avoids D_w entirely.
+
+Step 2 (reconstruct exterior pieces). For an interior mark on e,
+delete the parameter interval between the FIRST and the LAST visit to
+D_w (this removes the intervening excursions too). For a starting or
+terminal endpoint, use a one-sided neighborhood. These deleted
+intervals are pairwise disjoint along e. The retained pieces are
+compact arcs, each with interior in the open set
+ Omega = R^2 minus (union of closed D_w).
+They are pairwise disjoint, with distinct endpoints (every would-be
+intersection was a mark and is now off-limits).
+
+Now replace each retained piece by a polygonal arc inside Omega.
+Choose pairwise disjoint open neighborhoods U_P of the retained pieces,
+contained in Omega. A standard topological fact: a continuous path
+with compact image in an open set in the plane can be replaced, with
+the same endpoints, by a polygonal path in that open set. Pick short
+straight "spurs" from each disk boundary into the collar U_P at the
+endpoint, then connect the spur tip to a nearby interior point of the
+piece inside U_P, and replace the piece's interior between those points
+by a polygonal path in U_P. Join everything. The result is a family
+of polygonal arcs in Omega, each meeting disks only at its boundary
+endpoints, with interiors pairwise disjoint.
+
+Step 3 (fill disks). In a crossing disk D_w, join each of the two
+pairs of boundary endpoints by a straight chord. The four endpoints
+are distinct, no straight line contains four points of a circle, so the
+two chords meet in at most one point, and any meeting is transverse
+and interior. In a vertex disk D_w, choose a new vertex point not on
+any line through two boundary endpoints, and connect every boundary
+endpoint to it by a straight spoke; spokes meet only at the vertex.
+Assemble spokes, chords, and exterior polygonal pieces in the original
+edge order. Each resulting edge is a simple path: exterior pieces
+disjoint, at most one chord or spoke per disk, interior avoids all
+vertices. Every inter-edge crossing of the final drawing lies inside
+an original crossing disk, is transverse, and is unique in its disk
+(no triples). So the drawing is admissible, polygonal, straight near
+every vertex and crossing, and has no more crossings than the original.
+
+Step 4 (remove adjacent-edge crossings). Suppose two polygonal edges
+e = vu and f = vw share vertex v and cross at an interior point x
+(simple graph: u != w). Choose a small round disk about x meeting
+only the two straight strands of the crossing; contain no other mark or
+bend. Swap the portions of e and f from v up to this disk, and
+reconnect the swapped prefixes to the original suffixes with two
+disjoint chords inside the disk, pairing adjacent boundary endpoints.
+Inside the disk the crossing at x vanishes; outside the disk every
+old open track is used exactly once by the two new walks. The result
+is two polygonal WALKS (possibly with self-intersections).
+
+Subdivide these walks at all remaining crossings and bends, then
+repeatedly delete any closed sub-walk between two occurrences of the
+same subdivision vertex. Each deletion shortens a finite walk, so the
+process terminates, yielding simple polygonal paths. One checks
+admissibility is preserved:
+ - a remaining crossing of two tracks that end up in different new
+ walks is a straight-through passage counted exactly once;
+ - a remaining crossing of two tracks that end up in the same new
+ walk, or any loop deletion that creates a turn, occurs at a
+ point where no other edge is present (the original had no
+ triples or shared arcs), so no admissibility rule is violated;
+ - vertex and endpoint contacts are as before.
+Repeat Step 4 as long as an adjacent-edge crossing remains. Each
+iteration decreases the (finite) crossing count by at least 1, so the
+process terminates. Additionally, nudge the vertex positions or the
+straight stretches by a tiny generic amount to eliminate any residual
+triple crossings or tangencies.
+
+18.3 Result. Any admissible drawing can be replaced by an admissible
+polygonal drawing satisfying (a)-(d). In particular, any MINIMUM
+drawing can be normalized without loss of optimality.
-Each agrees with what we know from direct drawings and the historically
-verified cases (Kleitman for m <= 6, Woodall for K_{7,7}).
+==============================================================================
+PART X FURTHER READING
+==============================================================================
-The whole argument is self-contained: the only lemmas we did not fully
-prove from scratch are drawing normalization (Section 20, sketched in
-detail) and the standard facts of linear algebra listed in Section 7
-(proved or "obvious" as appropriate).
+19. FURTHER READING
+
+19.1 Crossing-number background.
+ J. Pach and G. Toth, "Which crossing number is it anyway?",
+ JCTB 80 (2000), 225-246.
+ P. Erdos and R. K. Guy, "Crossing number problems",
+ Amer. Math. Monthly 80 (1973), 52-58.
+
+19.2 The Zarankiewicz problem.
+ P. Turan, "A note of welcome", J. Graph Theory 1 (1977), 7-9.
+ (origin of the brick-factory question)
+ C. Zarankiewicz, Fund. Math. 41 (1955), 137-145.
+ (upper-bound drawing; incomplete optimality claim)
+ D. J. Kleitman, "The crossing number of K_{5,n}",
+ J. Combin. Theory 9 (1970), 315-323.
+ (exact for m <= 6; the vertex-deletion argument)
+ D. R. Woodall, "Cyclic-order graphs and Zarankiewicz's
+ crossing-number conjecture", J. Graph Theory 17 (1993), 657-671.
+ (verified K_{7,7} = 81)
+ E. de Klerk, J. Maharry, D. V. Pasechnik, R. B. Richter, G. Salazar,
+ "Improved bounds for the crossing numbers of K_{m,n} and K_n",
+ SIAM J. Discrete Math. 20 (2006), 189-202.
+ D. Brosch and S. C. Polak, "New lower bounds on crossing numbers of
+ K_{m,n} from semidefinite programming", Math. Programming 207
+ (2024), 693-715.
+ J. Balogh, B. Lidicky, S. Norin, F. Pfender, G. Salazar, S. Spiro,
+ "Crossing numbers of complete bipartite graphs", Procedia Comput.
+ Sci. 223 (2023), 78-87. (best prior lower bound:
+ cr(K_{n,n}) >= 0.9118 d_n^2 + o(n^4))
+
+19.3 Tools used here.
+ J.-P. Berrut and L. N. Trefethen, "Barycentric Lagrange
+ interpolation", SIAM Review 46 (2004), 501-517.
+ (barycentric weights);
+ V. Guruswami and S. Kopparty, "Explicit subspace designs",
+ Combinatorica 36 (2016), 161-185
+ (related determinant-multiplicity technique).
+
+19.4 Logical flow in one picture.
+
+ A drawing D of K_{m,n}
+ |
+ | normalize (Section 18)
+ v
+ Normalized minimum drawing D
+ |
+ | build J (Sections 9-12)
+ v
+ Antisymmetric block matrix J = (J^{ik})
+ |
+ | apply Phi (Sections 13-15)
+ v
+ Matrices R_ik = X_i - Y_k,
+ X_i - Y_i invertible,
+ rank(R_ik) <= c_ik
+ |
+ | rank-sum inequality (Section 8)
+ v
+ 2 d_m d_n <= 2 c(D), hence c(D) >= d_m d_n.
+ |
+ | even n: vertex deletion (Section 17)
+ v
+ d_m d_n <= c(D) for all m,n.
+ ==============
+ Equality follows from the upper bound (Section 4).
+
+19.5 Sanity checks on d_m d_n. The values:
+ m=n=1: 0 m=n=2: 0
+ m=n=3: 1 m=n=4: 4
+ m=n=5: 16 m=n=6: 36
+ m=n=7: 81 m=n=8: 144
+For m=n=3 this is 1, matching the geometric lower bound cr(K_{3,3}) >= 1
+(K_{3,3} is nonplanar). For m=n=4 this is 4, matching Kleitman's 1970
+computation. For m=n=7 this is 81, matching Woodall's 1993 computer
+verification. All entries grow like m^2 n^2 / 16, consistent with the
+balanced-axis construction of Section 4.
END.