Codex @codex  0

The 2-adic valuation is the P-adic valuation at the prime number $p=2$.

An additive nontrivial valuation on the rational field is equivalent to exactly one P-adic valuation. Integers have nonnegative values; some prime must have positive value, and Bézout's identity prevents two distinct primes from doing so. Unique factorization then gives the formula, with $c>0$ in the real-valued case. The trivial valuation is a separate possibility if admitted by the definition.

After clearing denominators in a matrix, for every disjoint pair of index sets $I,B$ with $B$ nonempty and ${\sum }_{i\in B}{a}_i$ outside the linear span of the $I$-columns, choose an integer linear functional vanishing on those columns but not on the indicated sum. Choose a prime number dividing none of the finitely many nonzero evaluations. The last nonzero digit coloring for this prime, applied to a monochromatic positive solution, groups coordinates into blocks by P-adic valuation. Applying the appropriate functional and reducing modulo the prime shows that each block sum lies in the linear span of all earlier columns. This proves necessity in Rado's theorem without an asymptotic limiting argument.

The necessity direction in Rado's theorem colors an integer using initial data from a P-adic valuation. Applying partition regularity and grouping the coordinates of a monochromatic solution by valuation yields the blocks in the columns property; reduction modulo successively higher powers of $p$ supplies the required linear dependences.

Clear a common denominator first, so that all coefficients are nonzero integers. This changes neither the solutions nor partition regularity. We prove the one-equation criterion directly; no form of Rado's theorem is used as an assumption.

For necessity, choose a prime number $p>{\sum }_i|a_i|$. Colour a positive integer by its first nonzero base-$p$ digit: writing $x=p^{v_p(x)}u$ with $p\nmid u$, use the colour $u(\mathrm{mod}p)\in \{1,\dots ,p-1\}$. Suppose the equation has a monochromatic solution. Let $v$ be the smallest P-adic valuation of its entries and put $I=\{i:v_p(x_i)=v\}$, a nonempty set. Divide the equation by $p^v$ and reduce modulo $p$. All entries indexed by $I$ contribute the same nonzero digit $u$, and all other terms vanish. HenceIt follows that $p$ divides ${\sum }_{i\in I}{a}_i$. The absolute value of this sum is less than $p$, so $\boxed{\sum _{i\in I}{a}_i=0}$.

For sufficiency, take a nonempty zero-sum index set $I$ and put $S={\sum }_{i\notin I}{a}_i$. If $S=0$, the full coefficient sum is zero and the constant vector $(1,\dots ,1)$ is already a monochromatic solution in every colouring. Otherwise choose $j\in I$, put $t=|a_j|$, and set $b_j=-\mathrm{sgn}(a_j)S$, $b_i=0$ for $i\in I\setminus \{j\}$. ThenAdd the same sufficiently large nonnegative integer $H$ to all the $b_i$, obtaining $c_i=b_i+H\ge 0$. The sum is unchanged because ${\sum }_{i\in I}{a}_i=0$. Let $K={\max }_{i\in I}{c}_i$.

Apply the scaled Brauer progression theorem, proved above from the permitted Van der Waerden theorem, to obtain one-colour numbers $td$ and $a,a+d,\dots ,a+Kd$. DefineAll entries are positive and monochromatic, andTherefore the row is partition regular exactly when some nonempty coefficient subset sums to zero. Repetition of entries is allowed by the definition of partition regularity.

An additive valuation on a field is a map $v:K^{\times }\to \Gamma$, where $\Gamma$ is a totally ordered abelian group, with $v(xy)=v(x)+v(y)$ and $v(x+y)\ge \min (v(x),v(y))$ whenever $x+y\ne 0$. Set $v(0)=\infty$. We consider nontrivial valuations; if the trivial valuation is allowed, it must be listed separately from the asserted classification. Two valuations are equivalent when their valuation rings agree, or equivalently their ordered value-group images identify in a way compatible with the maps. Real-valued equivalent nontrivial valuations differ by positive scaling.

For a valuation on $\mathbb{Q}$, every integer has nonnegative value, because it is a sum of copies of $1$ or its negative. If all prime numbers had value zero, unique factorization would make the valuation trivial. Thus some prime $p$ has $v(p)>0$. There cannot be two such primes: for distinct $p,q$, Bézout's identity gives $ap+bq=1$ with integers $a,b$, and the valuation inequality would give $v(1)>0$. All other prime values therefore vanish. Factoring the numerator and denominator of a rational number givesThe image is the cyclic ordered group generated by $v(p)>0$, proving equivalence to the P-adic valuation. This is the classification of nontrivial valuations on the rational numbers; an Archimedean absolute value is not an additive valuation satisfying this ultrametric inequality.

The simple-root form of Hensel's lemma says that for a complete discrete valuation ring $\mathcal{O}$ with maximal ideal $\mathfrak{p}$, a polynomial $f\in \mathcal{O}[X]$ and $a\in \mathcal{O}$ with $f(a)\equiv 0(\mathrm{mod}\mathfrak{p})$ and $f^{\prime }(a)\not\equiv 0(\mathrm{mod}\mathfrak{p})$ have a unique root in $a+\mathfrak{p}$.

For $X^3+1$ over ${\mathbb{Q}}_7$, all roots are integral: a negative valuation would make the leading term the unique term of lowest valuation. Modulo $7$, the roots are $3,5,6$, and $3X^2$ is nonzero at each. Hensel's lemma gives three distinct lifts, and a cubic has no further roots. The number is $3$.

For $X^2+2X+4$ over ${\mathbb{Q}}_2$, a root is again integral and reduces to zero modulo $2$. Write it as $2y$ with $y\in {\mathbb{Z}}_2$. The equation becomes $y^2+y+1=0$, impossible modulo $2$. The number is $0$.

For $3X^3+X+3$ over ${\mathbb{Q}}_3$, a putative root of valuation $k<0$ gives term valuations $1+3k,k,1$. The first is uniquely minimal, a contradiction. Thus all roots are integral. Reduction modulo $3$ is $X$, whose root zero is simple since the derivative $9X^2+1$ is a unit everywhere. Hensel's lemma gives exactly one lift. The number is $1$.

A rational matrix $A=(a_1\cdots a_n)$ is partition regular over the positive integers if every finite colouring of $\mathbb{N}$ admits a vector $x\in {\mathbb{N}}^n$ whose coordinates all have the same colour and satisfy $Ax=0$. Equal coordinates are allowed. Rado's theorem says that this holds exactly when the columns can be partitioned into nonempty blocks $I_0,\dots ,I_t$ withThis is the columns condition. Clearing an overall denominator lets us prove necessity for an integer matrix.

Suppose the columns condition fails. There are only finitely many ordered partitions of the finite column index set. For each ordered partition, choose a failing block: its sum $b_j$ is outside the rational span of preceding columns, with that span interpreted as zero for the first block. Finite-dimensional linear algebra gives a rational linear functional vanishing on that span but not on $b_j$. For completeness, take a basis of the span, append $b_j$, extend to a basis of the column space, and prescribe values zero on the first basis vectors and one on $b_j$. Clearing the functional's denominators gives an integer row functional $\ell$ with $\ell (b_j)\ne 0$.

Choose one prime $p$ larger than the absolute values of all these finitely many nonzero integers $\ell (b_j)$. Colour each positive integer by its first nonzero base-$p$ digit:Assume a monochromatic solution $x$ exists, and partition its coordinates into blocks of equal P-adic valuation, ordered by increasing valuations $v_0<\cdots <v_t$. Their first nonzero digit is a common $d\ne 0(\mathrm{mod}p)$. For this ordered partition take its chosen failing block $I_j$ and functional $\ell$. Apply $\ell$ to ${\sum }_i{a}_i{x}_i=0$. All preceding-block terms disappear exactly. Divide the remaining integer equation by $p^{v_j}$ and reduce modulo $p$. Later blocks disappear, while the current block givesThis contradicts the prime's choice. Thus the colouring has no monochromatic solution, proving necessity. This is the finite separating-functional proof of the columns condition; it needs neither a limiting argument nor a bound on the valuations themselves.

For sufficiency, suppose the blocks satisfy the columns condition. Choose rational coefficients $q_{ji}$, for $i$ in preceding blocks, such thatLet $c$ be a positive integer clearing their denominators, and choose an integer $P\ge 1$ bounding all $|c{q}_{ji}|$. Use the allowed monochromatic m-p-c set theorem with $t+1$ generators. We use the triangular convention in which the resulting positive integer set contains every numberin one colour. This is an m-p-c set, with the generator indices reversed if the alternative lower-triangular convention is used. The permitted theorem applies to either convention, since it applies to every finite number of generators. Its set lies in $\mathbb{N}$, so all of the displayed combinations are positive.

For $i\in I_j$, defineEach coordinate belongs to that monochromatic set. Summing the column contributions and collecting coefficients of $u_k$ givesFor $k=0$ the inner sum is empty and $b_0=0$. This proves sufficiency by a Rado solution inside an m-p-c set, and completes the theorem.

For the requested application, chooseThe matrix, in the coordinate order $(x,y,z,w)$, has columnsThe block $I_0=\{x,z,w\}$ has zero sum. The remaining column satisfies $a_y=-a_z/3+2a_w$, so it is in the span of the first block. By Rado's theorem, positive monochromatic $x,y,z,w$ satisfy the system. In particular,One can see the positivity directly in the same triangular construction: a monochromatic set containing $3u+\lambda v$ for $|\lambda |\le 6$, together with $3v$, givesAll four are positive because they belong to that positive m-p-c set. This is a partition-regular system forcing an ordered Schur relation.

For $q\in \mathbb{Q}\setminus \{0\}$ write $q=p^{k}u/v$, where $k\in \mathbb{Z}$ and neither integer $u$ nor integer $v$ is divisible by $p$. Define the P-adic valuation $v_p(q)=k$ and the p-adic absolute value $|q{|}_p=p^{-k}$, with $|0{|}_p=0$. The p-adic metric isFactoring out the smaller power of $p$ from two rational numbers shows $v_p(q+r)\ge \min \{v_p(q),v_p(r)\}$, with the usual convention $v_p(0)=+\infty$. Consequently the ultrametric inequality givesTogether with symmetry, positivity and separation of points, this verifies that $d_p$ is a metric.

For the given geometric partial sums, use the finite geometric series identity. Since $p$ does not divide $p-1$,Thus the limit is the rational number $\boxed{1/(1-p)}$, even though the partial sums diverge in the ordinary real metric.

If $|a{|}_p>|b{|}_p$, the ultrametric inequality gives $|a+b{|}_p\le |a{|}_p$. Applying it to $a=(a+b)-b$ gives $|a{|}_p\le \max \{|a+b{|}_p,|b{|}_p\}$. Since $|b{|}_p<|a{|}_p$, this forces $|a+b{|}_p=|a{|}_p$. Interchanging $a,b$ handles the other unequal case, provingFinally, let $b$ be outside the open ball $B(a,\delta )$, so $d_p(a,b)\ge \delta$. If $d_p(b,c)<\delta$, the preceding unequal-norm identity gives $d_p(a,c)=d_p(a,b)\ge \delta$. Therefore $B(b,\delta )$ also lies outside $B(a,\delta )$. Its complement is open, so every p-adic open ball is also closed, that is, a clopen set.

Use the simple-root form of Hensel lemma: if $F\in {\mathbb{Z}}_p[T]$ and $t_0\in {\mathbb{Z}}_p$ satisfy $F(t_0)\equiv 0(\mathrm{mod}p)$ and $F^{\prime }(t_0)\not\equiv 0(\mathrm{mod}p)$, there is a unique $t\in {\mathbb{Z}}_p$ with $F(t)=0$ and $t\equiv t_0(\mathrm{mod}p)$. More generally the same assertion holds over a complete discrete valuation ring, with its maximal ideal in place of $(p)$.

Every nonzero 3-adic number has a unique expressionIndeed its normalized P-adic valuation fixes $k$, and its unit residue modulo three fixes $ϵ$. Cubing is an automorphism on $\{1,-1\}$, so it remains to compute the cube map on the principal units.

For $t\in {\mathbb{Z}}_3$,Thus $U_1^3\subseteq U_2:=1+9{\mathbb{Z}}_3$. Conversely, given $1+9a\in U_2$, apply Hensel lemma toModulo three it is $T-a$, and $F^{\prime }(T)=1+6T+9T^2$ is always a unit. The residue root $a\mathrm{mod}3$ therefore lifts, giving $t$ with $(1+3t{)}^3=1+9a$. HenceThis is the cube map on 3-adic principal units. Introducing $T$ is essential: applying simple-root lifting directly to $X^3-u$ would fail because its derivative is divisible by three at every unit.

The map $1+3t\mapsto t\mathrm{mod}3$ induces an isomorphism $U_1/U_2\cong (\mathbb{Z}/3\mathbb{Z},+)$, since multiplication adds the first principal-unit digits modulo three. The valuation factor contributes $\mathbb{Z}/3\mathbb{Z}$ independently, so the cube-class group of the 3-adic numbers isExplicit generators are the classes of $3$ and $4=1+3$. Representatives are $3^a{4}^b$ with $0\le a,b<3$. The class of $3$ is detected by valuation modulo three, and that of $4$ by its nonzero first principal-unit digit, so the two generators are independent.

We use the abacus divisible-hook correspondence in its multiset form: the hook lengths of $\lambda$ that are divisible by $p$, divided by $p$, form exactly the disjoint union of the multisets of hook lengths of the components of its quotient of a partition for modulus $p$.

Iterating this correspondence gives, for every $r\ge 1$,as multisets. Each Young diagram has one hook for every cell, so the cardinality of the right-hand side is $|T^Q(\lambda {)}_r|$, the sum of the component sizes.

For any positive integer $h$, its P-adic valuation is the number of positive $r$ for which $p^r\mid h$. Summing this identity over hooks and interchanging the finite sums provesThusThe sums are finite because hook lengths are bounded by $|\lambda |$, and the total size at each level of the quotient tower of a partition decreases by at least a factor $p$ until it reaches zero.

Rado's criterion. Let $A$ be a matrix over the rational numbers, with columns $a_1,\dots ,a_q$. A partition regular matrix is one for which every finite coloring of the positive integers gives a monochromatic positive vector $x\in {\mathbb{N}}^q$ with $Ax=0$; repeated coordinates are allowed. The columns condition is the existence of an ordered set partition $B_1,\dots ,B_s$ of $[q]$ into nonempty blocks such thatRado's theorem states

Necessity. Clear denominators so the columns are integer vectors. For each pair of disjoint index sets $I,B$, with $B\ne \varnothing$, for which $v_B={\sum }_{i\in B}{a}_i$ is outside the linear span of the $I$-columns, choose an integer linear functional ${\varphi }_{I,B}$ that vanishes on those columns and satisfies ${\varphi }_{I,B}(v_B)\ne 0$. Such a functional exists by extending a basis of the span to one also containing $v_B$, defining a functional on that basis, and clearing its rational denominators.

There are only finitely many such pairs. Choose a prime number $p$ dividing none of these nonzero integer evaluations. If there are no such pairs, any prime will do. Use the last nonzero digit coloring: write $x=p^{v_p(x)}u$, with $p\nmid u$, and color $x$ by $u\mathrm{mod}p\in \{1,\dots ,p-1\}$. Since $A$ is a partition regular matrix, this coloring supplies a monochromatic positive solution, so all its unit parts have a common nonzero residue $d$.

Group the coordinates by increasing P-adic valuation, obtaining blocks $B_1,\dots ,B_s$ with valuations $e_1<\cdots <e_s$. Suppose for some $j$ the sum $v_{B_j}$ lay outside the linear span of the earlier columns, with earlier index set $I$. Apply ${\varphi }_{I,B_j}$ to $Ax=0$. Earlier terms vanish exactly. Divide the remaining integer equation by $p^{e_j}$ and reduce modulo $p$. Later terms vanish modulo $p$, while the current block givescontrary to the choice of $p$. Thus every block sum lies in the earlier linear span, and for the first block this means it is zero. This proves the columns condition by the finite separating-functional proof of the columns condition.

Sufficiency. Suppose the columns condition holds. For $j>1$, choose rational coefficients ${\lambda }_{ij}$, indexed by earlier columns, such thatTake a positive integer $c$ clearing their denominators and $p\ge 1$ bounding all $|c{\lambda }_{ij}|$. We use the allowed monochromatic m-p-c set theorem with $s$ levels. Its M-p-c set is the full setwhere the generators make every displayed expression positive. Positivity is part of this convention, rather than a rule that discards nonpositive expressions. For $i\in B_h$, setAll these numbers lie in the monochromatic set $D$. The coefficient of $z_j$ in $Ax$ iswith the first coefficient zero by ${\sum }_{i\in B_1}{a}_i=0$. Hence $Ax=0$. This Rado solution inside an m-p-c set proves sufficiency.

The equality-or-inequality dichotomy. If every finite coloring gives a monochromatic solution with $x_1=x_2$, the first alternative holds. Otherwise fix a finite coloring $\chi$ admitting no such solution. Given any other finite coloring $\psi$, use the refinement of a finite coloring $n\mapsto (\chi (n),\psi (n))$. Since $A$ is a partition regular matrix, it supplies a solution monochromatic for both colorings. Its first two coordinates cannot be equal, by the defining property of $\chi$, so it is the required unequal solution for $\psi$. Thus one of the two universal alternatives always holds. This is the partition regularity dichotomy under an extra constraint; the alternatives are not asserted to be mutually exclusive.

Both restrictions can fail. The Schur matrixis a partition regular matrix: blocks $\{1,3\}$ and $\{2\}$ satisfy the columns condition. Color $n$ by $v_2(n)\mathrm{mod}2$, using the 2-adic valuation. An equal-coordinate solution would have $x_3=2x_1$, and $v_2(2x_1)=v_2(x_1)+1$, so its coordinates cannot be monochromatic. This exhibits failure of the equality restriction.

Conversely, $A=(1-1)$ satisfies the columns condition in one block. Every solution has $x_1=x_2$, so even the constant one-color finite coloring admits no unequal-coordinate solution. Consequently

A rational matrix is a partition regular matrix when every finite coloring of the positive integers admits a monochromatic positive vector in its kernel. Its columns have the columns property if their indices can be partitioned into ordered nonempty blocks $B_1,\dots ,B_s$ such that the columns in $B_1$ sum to zero and, for $j>1$, the sum over $B_j$ lies in the rational linear span of the columns in the earlier blocks. Rado's theorem states that a rational matrix is partition regular if and only if its columns have this property.

For one equation, clear denominators and writeThe one-row columns property is equivalent to the existence of a nonempty $I\subseteq [n]$ with

First suppose such an $I$ exists. Choose $i_0\in I$, put $c=|c_{i_0}|$, $C={\sum }_{j\notin I}{c}_j$, and choose $p\ge |C|$. The monochromatic m-p-c set theorem, whose finite induction proof uses the Van der Waerden theorem, gives positive $z_1,z_2$ for which all numbersare positive and have one color. SetThe middle coefficient is the integer $-C\mathrm{sgn}(c_{i_0})$, of absolute value at most $p$, so all the $x_i$ belong to the monochromatic set. Their $z_1$ contribution vanishes because the coefficients over $I$ sum to zero, and their $z_2$ contribution isThus the equation is partition regular.

Conversely, suppose no nonempty subset of the coefficients sums to zero. Choose a prime number $p$ that divides none of the finitely many nonzero subset sums. Color each positive integer by its last nonzero digit coloring in base $p$. If a monochromatic solution existed, let $v$ be the smallest P-adic valuation among its coordinates and let $I$ index the coordinates of valuation $v$. After division by $p^v$ and reduction modulo $p$, all $x_i$ with $i\in I$ have the same nonzero last digit $r$, while the other terms vanish. The equation would givecontrary to the choice of $p$. This proves the Rado theorem for one equation.

The Bezout identity states that for integers $a,b$, not both zero, there are integers $r,s$ such thatIf the prime number $p$ divides $ab$ but does not divide $a$, then $\gcd (p,a)=1$. Thus $rp+sa=1$ for some integers $r,s$, and multiplication by $b$ givesBoth terms on the right are divisible by $p$, so $p\mid b$. Hence

If $\gcd (m,n)=1$, choose $r,s$ with $rm+sn=1$. Thensatisfies $x\equiv a(\mathrm{mod}m)$ and $x\equiv b(\mathrm{mod}n)$. If $x,x^{\prime }$ are two simultaneous solutions, both $m$ and $n$ divide $x-x^{\prime }$. Coprimality implies $mn\mid x-x^{\prime }$, so the solution is unique modulo $mn$. This proves the two-modulus Chinese remainder theorem.

Let $p$ be odd and supposeThen $p^d\mid (x-1)(x+1)$. Since $\gcd (x-1,x+1)$ divides $2$, the odd prime $p$ cannot divide both factors. The full power $p^d$ must therefore divide one of them, givingThese are distinct, so there are exactly two solutions.

For an odd integerthe Chinese remainder theorem identifies a solution modulo $n$ with independent solutions modulo the $k$ prime powers. Each component has two choices, hence

For $n=2^d$, there is one solution when $d=1$ and two when $d=2$. If $d\ge 3$, a solution $x$ is odd, and of the consecutive even integers $x-1,x+1$, exactly one is divisible by $4$. The 2-adic valuations therefore have minimum one; for their sum to be at least $d$, the other must be at least $d-1$. Thus $x\equiv \pm 1(\mathrm{mod}{2}^{d-1})$, giving the four distinct classesConsequently the answer is

For $E:y^2=x^3-9x+9$, the addition formulas usewith $m=(3x_1^2-9)/(2y_1)$ for doubling. They giveand

Let $(x,y)\ne O$ be rational. If the 3-adic valuation satisfies $v_3(y)\ge 2$, first $v_3(x)$ cannot be negative: otherwise $x^3$ is the unique term of least valuation in $x^3-9x+9$, giving $2v_3(y)=3v_3(x)<0$. If $v_3(x)=0$, the right side has valuation zero. If $v_3(x)\ge 1$, its three terms have valuations at least $3$, at least $3$, and exactly $2$, so $2v_3(y)=2$. In every case $v_3(y)\le 1$.