COORDINATES — which coordinate system reads which operation

The object: the integers written in coordinate systems, each writing a number as a tuple of coordinates by a bijection, and above all in the three classical ones: residues at a set of primes, indices (a discrete logarithm in each channel) and positional digits, defined on Z/M for residues (M a product of distinct primes), on the units U(M) for indices and on Z/b^j for j digits in base b. The exponent vector, the logarithm the integers themselves carry, stands beside them in the table below, uncounted: on a finite prime set it is no bijection. Each system reads some operations cheaply, and an operation it does not read cheaply is one of its walls. This page says which pair of operations each system reads, proves that on Z/M no system with two coordinates or more reads addition and multiplication coordinate by coordinate with the sign a function of one coordinate, names three kinds of wall, names for most walls, here and in SIZE, the hypothesis each needs or uses, and reads the Internet checksum, where digits and residues meet, one prime at a time.

SYSTEM             +                  ×              POWERING       SIZE
residues mod M     channel-local      channel-local  exponent read  walled
 (M squarefree)                                      mod λ, y ≥ 1
indices on U(M)    one table per      addition       scaling        —
                    channel,
                    compatible with
                    no proper
                    quotient but Z/1
exponent vectors   walled             addition       scaling        walled
digits in base b   one carry bit,     not automatic  —              compared
                    no bounded set                                   top first

λ = lcm(p − 1) over the channels, Carmichael's exponent of a squarefree M, and the table's y ≥ 1 is the exponent of a power x^y. Size is walled under residues once M has two channels or more (SIZE: The size wall); at a prime M the one channel reads it. Size under indices and powering under digits are not decided here, and their cells are left empty (—). The exponent vector is read on a finite prime set, as a residue system is read at a finite set of channels, and there size is walled outright: 1 and every prime outside the set share the zero vector.

Three kinds of wall appear. Size under residues at two channels or more is an information wall: no channel-local read, of any size, decides it (SIZE: The size wall). Addition under indices is a structure wall: the data sits in one channel, but as a table compatible with no proper quotient but Z/1 (proved below, p ≥ 5). Powering under residues is a type wall unless λ | M: the exponent is read mod λ, which Z/M carries exactly when λ | M (proved below).

The two-readings criterion

Tier: criterion.
Verifier: proof; coordinates.py::section_b.

Greedy numeration on a scale 1 = T₀ < T₁ < T₂ < ⋯ writes n with digits d_i, taking at each step from the top the largest multiple of T_i that fits. The low prefix Σ_{i<j} d_i T_i equals n mod T_j for every n and j iff the scale is a divisibility chain, T_j | T_i for i ≥ j. On every scale, chain or not, digit strings compared from the top are compared as numbers; that half is known (Shallit, Numeration systems, linear recurrences, and regular sets, Waterloo report 1991, sec. 2; ICALP 1992): the greedy representation is order-preserving.

Proof. Greedy leaves the part of n below position i under T_i. On a chain the prefix is under T_j and n minus it is a sum of multiples of T_i, i ≥ j, each 0 mod T_j. Conversely n = T_i is the single digit 1 at i, prefix 0, which forces T_j | T_i. For order, at the first differing position d_i < d′_i, and what is left of the smaller number is below T_i.

So size and order come with greedy and residues come with the chain. The scales on which the two readings coincide are exactly the divisibility chains: a positional base, and every mixed radix on a chain. Zeckendorf keeps only the greedy half; a residue system keeps only the residue half. The script checks the criterion on all 9,139 scales (1, T₁, T₂, T₃) with T₃ ≤ 40 and all 3,876 scales of length 5 up to 20, and greedy order on the first set, each scale at every n up to twice its top term, which holds the witness n = T_i.

The carry wall

Tier: theorem.
Verifier: proof; coordinates.py::section_a.

In base b, no bounded set of digit positions, fixed relative to j as j grows and joined by a fixed block of low digits, reads digit j of x + y. One carry bit, read from the least significant digit up, computes the whole sum.

Proof. Given the set, pick a position ℓ < j outside it and above the low block, which exists once j is large. Let x = Σ_{i=ℓ}^{j−1} (b − 1)bⁱ and compare y = b^ℓ with y′ = 0. The inputs differ only at ℓ, and x + y = b^j has digit j equal to 1 while x + y′ < b^j has digit j equal to 0.

No synchronous automaton recognizes the graph x·y = z in any base. Addition is recognized by one, the carry bit its state, so a second for x·y = z would make (N, +, ×), N the natural numbers, an automatic structure; an automatic structure has a decidable first-order theory (B. R. Hodgson, Décidabilité par automate fini, Ann. Sci. Math. Québec 7 (1983) 39–57; B. Khoussainov and A. Nerode, Automatic presentations of structures, Lecture Notes in Comput. Sci. 960 (1995) 367–392), and (N, +, ×) does not (A. Church, An unsolvable problem of elementary number theory, Amer. J. Math. 58 (1936) 345–363).

Addition and multiplication each decide

Tier: known.
Source: Presburger 1929; Mostowski 1952; Putnam 1957; Villemaire 1992; Korec 1993 and 1995; Bès 1997; all as given in Bès, A survey of arithmetical definability (Proposition 5, Theorems 23 and 36, the notes on Pascal triangles); J. Robinson, J. Symbolic Logic 14 (1949) 98.

(N, +) has a decidable theory (Presburger), and so does (N∖{0}, ×). Through the exponent vector, (N∖{0}, ×) is the weak direct power of (N, +): one copy at every prime, all but finitely many coordinates zero. A weak power of a decidable structure is decidable (Mostowski). So every valuation at every prime, read with no addition, costs no decidability, and on the additive side neither does reading size, since < is definable in (N, +); beside × it does, since < defines the successor and × with the successor defines + (J. Robinson, 1949): z = x + y iff (xz + 1)(yz + 1) = z²(xy + 1) + 1 with z ≠ 0, or x = y = z = 0, as the identity reduces to (x + y)z = z². (N, +, ×) is undecidable though neither half is. The undecidable expansions of (N, +) that the survey charts add a trace of multiplication; a noncomputable set is undecidable by its membership sentences alone and needs none. The squares define × (Putnam), and so do the predicates V_k(x), the largest power of k dividing x, at two multiplicatively independent bases (Villemaire). Pascal's triangle mod n, B_n(x, y) = C(x + y, x) mod n, reads at each p dividing n whether adding x and y in base p carries (Lucas), and is decidable beside + at a prime power but defines + and × by itself once n has two primes, as at 6 (Korec). Each of these definitions is the multiplicative side meeting the additive one. Residues at finitely many primes add only periodic sets, which (N, +) already defines, so even joined with size they decide.

The suffix and floor reads

Tier: criterion.
Verifier: proof; coordinates.py::section_s.

For m ≥ 2, in base b [m | n] is a function of the last j digits iff m | b^j, so some suffix reads it iff rad(m) | rad(b). On a chain of moduli 1 = M₀ | M₁ | M₂ | ⋯, at depth t with M_t ≥ 2 and lookahead c ≥ 0, ⌊n/m⌋ mod M_t is a function of n mod M_(t+c) iff m·M_t | M_(t+c).

Proof. n and n + b^j share the suffix, and at n = 0 they disagree unless m | b^j; conversely, if m | b^j the suffix n mod b^j fixes n mod m. For the floor, write M′ = M_(t+c). The step ⌊(n + M′)/m⌋ − ⌊n/m⌋ is the constant M′/m when m | M′, which is 0 mod M_t iff m·M_t | M′. Otherwise it takes both values ⌊M′/m⌋ and ⌊M′/m⌋ + 1 as n runs over the residues mod m, and two consecutive integers are never both 0 mod M_t.

On the primorial chain M_t = p₁⋯p_t this reads ⌊n/m⌋ at depth t iff m is squarefree with every prime factor above p_t, and the least lookahead is exactly π(P(m)) − t, P(m) the largest prime factor of m. So division by m is read only at the depths t with p_t below m's least prime, and at no depth from that prime's on. Divisibility behaves the other way: every squarefree m divides the primorials from some depth on. At a fixed base the two reads coincide, both holding iff rad(m) | rad(b); on the primorial chain they part. The script finds exactly the twelve readable cells (t, m) the criterion predicts for 2 ≤ m ≤ 30 and M_(t+c) ≤ 2,310.

The Internet checksum

Tier: theorem.
Verifier: proof; checksum.py::section_r; checksum.py::section_c; checksum.py::section_b; checksum.py::section_u; checksum.py::section_w.

Where digits and residues meet: at M = b − 1 a base-b numeral is congruent to its digit sum, since b ≡ 1. The Internet checksum is that meeting at b = 2¹⁶. RFC 1071 sums a message's 16-bit words in ones' complement and sends the complement; its appendix (IEN 45) reads the sum as the remainder mod 2¹⁶ − 1, the end-around carry as the reduction, and the complement is negation. The ones' complement +0 and −0, 0x0000 and 0xFFFF, are the two representatives of the class 0. The modulus is 65535 = 3 · 5 · 17 · 257, the Fermat primes F₀ to F₃, so the checksum is four checksums, one per prime.

Each prime reads a bit by its position alone. At the Fermat prime F_j = 2^(2^j) + 1, 2^(2^j) ≡ −1, so a bit at position a of any word counts at F_j as ±2^(a mod 2^j), with sign (−1)^⌊a/2^j⌋: the four primes read the position mod 2, 4, 8 and 16, and none reads which word holds it. Three properties of the standard follow, one prime at a time.

The script checks the fold at every sum of two words, the per-prime reading at every position, the swap on 500 random messages, both updates on 500 random one-word changes, one in five steered to a zero sum, and the three computations at the two edges above, each prime's miss set by residue arithmetic at every pair of positions within a word for same-way and opposite flip pairs, and the missed share over every pair of bit positions and both values of each flipped bit, on one message of each length 1 to 4 words, the checksum recomputed each time.

The valuation row

Tier: theorem.
Verifier: proof; coordinates.py::section_v.

Write n by its exponent vector (v_p(n))_p. Multiplication is the coordinatewise sum. Addition is walled: for every finite prime set W, no function of the W-coordinates of x and y gives any W-coordinate of x + y.

Proof. Fix p ∈ W. By the CRT there is y_u with y_u ≡ p^u − 1 mod p^(u+1) and y_u ≡ 1 mod the other primes of W. Then y_u and 1 both have the zero vector on W, while v_p(1 + y_u) = u takes every value u ≥ 1.

The index coordinates

Tier: property.
Verifier: coordinates.py::section_i.

For squarefree M, U(Z/M) is the product of the cyclic (Z/p)^*. A primitive root per channel gives the bijection U(Z/M) → ∏ Z/(p − 1) onto the index ring, under which multiplication is addition and powering is scaling. x is an e-th power iff gcd(e, p − 1) divides its index at every p, with ∏ gcd(e, p − 1) roots, and x is a square mod p iff its index there is even. The exponent of the index ring is λ = lcm(p − 1), below ∏(p − 1) once two odd primes are present, so no rung from Z/30 on (TOWER) has a primitive root: the index exists only channel by channel. The script checks the bijection at M = 510510 = 2·3·5·7·11·13·17 (92,160 units) and the root counts there, 1,440 squares with 64 roots each and 10,240 cubes with 9.

The Zech wall

Tier: theorem.
Verifier: proof; coordinates.py::section_z.

At a channel p with primitive root g, addition in index coordinates is the unary table ζ(i) = ind(1 + gⁱ), defined off the one i with gⁱ = −1. For every p ≥ 5, ζ is compatible with no quotient Z/(p − 1) → Z/q, q | p − 1, 2 ≤ q ≤ (p − 1)/2, so it agrees with no polynomial on Z/(p − 1) where it is defined.

Proof. Indices mod q sort (Z/p)^* into the cosets of the subgroup H of index q, of order h = (p − 1)/q ≥ 2. Compatibility says (1 + wx)/(1 + x) lies in H for every w ∈ H and every x ∈ (Z/p)^* outside {−1, −1/w}, which is p − 3 values when w ≠ 1. Fix w ≠ 1. For z ∈ H, 1 + wx = z(1 + x) reads x(w − z) = z − 1: z = w has no solution, z = 1 gives x = 0, and every other z gives one admissible x. So exactly h − 2 < p − 3 of the required x comply, and each other x gives two indices equal mod q whose Zech values are not. A polynomial over Z/(p − 1) respects every quotient.

The index map is a channel-local bijection, so addition, where the sum is a unit, stays channel-local in index coordinates, and the locality criterion (SIZE: The locality criterion) cannot see this wall. It costs one table of p − 2 entries per channel. The size wall costs what no channel-local table of any size supplies. The script checks all 263 pairs (p, q) with p < 200, and every w ≠ 1 when p < 60.

The support log

Tier: theorem.
Verifier: proof; coordinates.py::section_g.

x^(λ+1) = x for every x in Z/M, λ Carmichael's exponent of M, iff M is squarefree. Then every x is the pair (supp x, the indices of x on supp x), supp x the set of channels where x ≠ 0. Multiplication intersects supports and adds indices, x^λ is the idempotent of supp x, and for M > 2 the meadow inverse x^(λ−1) (LOGIC: The meadow) negates the indices (at M = 2, λ = 1 and 0⁰ = 1).

Proof. On a squarefree M each channel is a field and p − 1 | λ. When p² | M, M/p is nonzero with square 0, so its (λ + 1)-th power is 0. The rest is the index coordinates applied on each support, where x^λ is 1 at every channel of the support and 0 off it.

So the logarithm reaches the whole ring as a pair, the support and an index, and log 0 = −∞ is a drop to a smaller support. On the units the index coordinate reads × as addition. Off them only the zero map into a group does: a map f into a group with f(0) + f(x) = f(0·x) = f(0) is 0. The support stands in its place.

The exponent wall

Tier: theorem.
Verifier: proof; coordinates.py::section_e.

For a prime p ≥ 3 and y ≥ 1, x^y is not a function of (x mod p, y mod p): at every such y the pairs (y, y + p) disagree exactly at the p − 2 residues x outside {0, 1}. It is a function of x mod p and y mod (p − 1) for positive y only. At p = 2, x^y = x for every y ≥ 1, so there is no wall there, and the only failure of either reading is 0⁰ = 1. On a squarefree M, x^y at y ≥ 1 is a function of (x mod M, y mod M) iff λ | M, as at M = 6, 42 and 1806.

Proof. x^(y+p) = x^y·x^p = x^(y+1) by Fermat, which differs from x^y iff x^y(x − 1) ≠ 0. For positive y, x^(y+p−1) = x^y at every x, 0 included, while 0⁰ = 1 and 0^(p−1) = 0. On a squarefree M, x^(y+λ) = x^(y−1)·x^(λ+1) = x^y at y ≥ 1 by the support log, so λ | M reads the exponent mod M; when λ ∤ M, a unit g of order λ, which the unit group's exponent supplies, has g^(1+M) ≠ g.

So the exponent of a power belongs to the index ring, with the zero exponent excluded, and the residue reading reads its base, and its exponent only when λ | M. The script checks the witnesses at p = 3 to 13, and on every squarefree M ≤ 300 that the exponent is read mod M exactly at M = 2, 6 and 42.

The rigidity dichotomy

Tier: theorem.
Verifier: proof; coordinates.py::section_r.

On Z/M a coordinate system is a bijection x ↦ (x_1, … , x_r) onto a product of sets of two elements or more, and it reads an operation coordinate by coordinate when each coordinate of the result is a function of the same coordinate of the arguments. The systems with two coordinates or more that read + coordinate by coordinate are exactly, up to relabelling each coordinate's values and reordering the coordinates, the coprime factorizations of Z/M into two factors or more, each above 1. Each of them reads × coordinate by coordinate as well, and walls size: the sign [x ≥ M/2] is a function of no coordinate. So no coordinate system with two coordinates or more reads + and × coordinate by coordinate with the sign a function of one coordinate; the one-coordinate system Z/M reads all three and splits nothing. On the unit group alone, multiplication is not rigid: U(M) can have decompositions that cross the channels, three of four at M = 30.

Proof. When + is read coordinate by coordinate, each coordinate, relabelled, is a surjective group homomorphism, so the system is an isomorphism onto a product of quotients, which is an internal direct sum of subgroups of Z/M. A cyclic group has one subgroup per order, and two of them meet in the subgroup whose order is the gcd, so the summands have pairwise coprime orders a_i with product M. Each summand is an ideal, so a product of elements of two different summands is 0, and × splits by summand. For a summand of order a < M, the elements 0 and a⌈M/(2a)⌉ share that coordinate while the sign [x ≥ M/2] reads 0 and 1 (SIZE: The size wall). U(30) ≅ C₂ × C₄ has four direct decompositions, and three cross the channels: two take the C₄ {1, 17, 19, 23}, against {1, 11} or {1, 29}, and the third pairs the channel's C₄ {1, 7, 13, 19} with the C₂ {1, 29}.

Each pair of operations has its own home: (+, ×) the residues, (×, powering) the indices, and (+, size) the digits, where the + read is a scan and not a bounded set of digit positions. The Zech wall is the price of the index row and the size wall the price of the residue row. The script counts 4, 4, 1 and 14 additive decompositions of Z/30, Z/60, Z/12 and Z/210, one per coprime factorization into two factors or more.

The bearers

Tier: theorem.
Verifier: proof; coordinates.py::section_p; size.py::section_h.

A bearer of a wall, or of a law the walls rest on, is a structure on which it holds. Every bearer in the table below is a finite ring or a finite abelian group, and none needs the rungs. The carry wall and the addition wall of the valuation row live on the integers themselves, outside the table. Conjunctive and failing maximally are SIZE: The conjunctive split's terms. There are two kinds of row. An exact row names a hypothesis its wall or law needs: on a structure without it, it fails. A sufficient row names only the hypothesis its proof uses.

BEARER                      WALL / LAW                            KIND
a cyclic group and a        sign and orientation hidden           exact
 proper quotient             (SIZE, the hiding lemma)
any composite Z/M           quantifying over channels:            exact
                             no polynomial computes [x = 0]
one field, p ≥ 5            the Zech wall                         exact
squarefree, λ ∤ M           the exponent wall                     exact
two proper windows          order fails maximally                 exact
two cyclic groups of        the order-divisibility wall:          exact
 non-coprime orders          ord(x) | ord(y) not conjunctive
squarefree                  x^(λ+1) = x; the meadow               exact
squarefree                  channel-local = polynomial            sufficient

Proofs of the rows not proved elsewhere on these pages. The quantifier wall, LOGIC: The pair's wall on quantifying over channels, is read here at the hypothesis it needs, M composite. A polynomial on Z/M is compatible with every quotient Z/A, and a proper divisor A > 1 would need [0 = 0] ≡ [A = 0] mod A, that is 1 ≡ 0; at a prime [x = 0] is 1 − x^(p−1), so the wall needs the composite. For order, a window A, the reading x mod A at a proper divisor A of M, suffices, since u = s < A and v = s′ + A ≤ 2A − 1 < M realize every residue pair (s, s′) at A with u ≤ v; no field is used, and neither is coprimality, which only makes two windows whose product is M a coordinate system. With one coordinate, Z/M itself, order is read. On C_n1 × C_n2 the relation ord(x) | ord(y) is conjunctive iff gcd(n1, n2) = 1, and fails maximally iff n1 = n2. Its first projection is the set of pairs with ord x₁ | lcm(ord y₁, n2), all of them iff n1 | n2, and its second, by symmetry, is full iff n2 | n1. When gcd(n1, n2) = 1, ord x₁ is prime to n2, so the projection is ord x₁ | ord y₁, and since ord x is the product of its coprime parts the conjunction is the relation. At a prime r dividing both, x of order r in the first factor against y = 0 lies in both projections but not in the relation. The least bearer by order where the relation fails without failing maximally is C₂ × C₄ = U(15). On the rungs the order-divisibility wall first appears at Z/30, whose channels 3 and 5 are the first two with unit orders 2 and 4 sharing a prime, and that pair is the bearer U(15) itself.

The locality criterion's row is sufficient only: its proof uses the fields, yet Z/4 still has as many polynomial maps as maps whose value mod 2 depends only on the argument mod 2, 64, and Z/8 is the first failure (size.py::section_l). The script checks the quantifier wall against the whole span of polynomial functions at Z/4, Z/6, Z/8 and Z/9 (Kempner's counts 64, 108, 1,024 and 19,683; Trans. Amer. Math. Soc. 22, 1921), order at Z/6 and at Z/36 through the windows 4 and 9, and the order-divisibility relation on all 45 pairs 2 ≤ n1 ≤ n2 ≤ 10.