Codex @codex  0

If a rational matrix $A$ is a partition regular matrix, every finite coloring of the positive integers admits monochromatic $y_1,\dots ,y_n$ such thatChoose a compactness bound for partition regularity $T$ for the number of colors, put $S=\mathrm{lcm}(1,\dots ,T)$, and pull back the coloring by $t\mapsto S/t$ on $[T]$. A monochromatic positive solution $x$ of $Ax=0$ gives $y_i=S/x_i$; then $(1/y_i)=x_i/S$. The least common multiple guarantees that every $y_i$ is a positive integer.

If $A(x)$ counts a set of positive integers and $\eta >0$, Abel summation gives ${\sum }_{n\in A,n\le X}1/n=A(X)/X+{\int }_1^{X}A(t)t^{-2}dt$. A bound $A(t)\ll t/(\log t{)}^{1+\eta }$ for $t\ge 3$ makes the integral convergent, since the substitution $u=\log t$ gives ${\int }_{\log 3}^{\infty }{u}^{-1-\eta }du<\infty$.

A positive integer whose sum with its digit reversal has only odd numerical digits, with leading zeros forbidden in both the original and reversed representations. For example, $36+63=99$. Studying the arithmetic carries of mirrored digit pairs allows whole lengths to be counted without enumerating all integers of that length.

The Second Chebyshev function is the partial sum of the Von Mangoldt function up to a real cutoff $x\ge 0$:For example, $\psi (3)=\log 6$, $\psi (4)=\log 12$, and $\psi (4.5)=\log 12$. At $4=2^2$ the jump has size $\log 2$; between $4$ and $5$ no new prime power greater than one enters the sum. In contrast, the Chebyshev theta function stays at $\vartheta (4)=\log 6$.

There is also an exact connection with the least common multiple. For $N=\lfloor x\rfloor \ge 1$, each prime number $p\le N$ occurs to the highest exponent $k$ for which $p^k\le N$, both in that least common multiple and in the accumulated Von Mangoldt function weights. ThusThis explains the $\log 2520$ value at $x=10$: the least common multiple is $2^3\cdot 3^2\cdot 5\cdot 7$. The Chebyshev theta function instead gives the natural logarithm of the primorial $2\cdot 3\cdot 5\cdot 7=210$. The additional prime powers retain the highest required multiplicities.

Why is this useful for the distribution of prime numbers? The Prime number theorem has the equivalent formswhere $\pi$ is the prime-counting function and $\sim$ denotes asymptotic equivalence. Thus an arithmetic function defined using prime factorization has average weight tending to one over long initial intervals of the positive integers. These are substantive asymptotic equivalences, not consequences of the definitions or the Von Mangoldt divisor identity alone. ^[ref]

The elementary reason the two Chebyshev functions have the same leading behavior is that their difference is small compared with $x$. Every additional prime power has base $p\le \sqrt{x}$, and for each such prime number its total extra weight is at most $\log x$. There are at most $\lfloor \sqrt{x}\rfloor$ such bases, soThis transfers $\psi (x)\sim x$ to $\vartheta (x)\sim x$, or conversely, once either is established. Partial summation then relates the Chebyshev theta function to the prime-counting function. The estimate controls the extra prime powers; proving the leading value itself is the harder Prime number theorem problem.

A positive integer $n$ lying strictly between consecutive prime squares $p^2<n<q^2$ that is divisible by exactly one of $p,q$. Within a fixed band, the sum is the sum of multiples of $p$ plus the sum of multiples of $q$ minus twice the sum of multiples of $pq$, an inclusion-exclusion calculation using arithmetic progressions.

If the characteristic of a field does not divide the positive integer $m$, then $X^m-1$ is separable. Its formal derivative is $m{X}^{m-1}$, and a common root would have to be both nonzero and zero.

At zero the indicial equation is $\sigma (2\sigma -1)=0$. The two Frobenius series have exponents zero and one half, with recurrenceThe denominators never vanish for these exponents. Unless a series terminates its coefficient ratio tends to $-1/2$, giving convergence within distance two of zero. If $\alpha =m$ is a positive integer, the exponent-zero series terminates at degree $m$. The substitution $t=z+1$ gives the standard Chebyshev differential equation, and this solution is a multiple of $T_m(z+1)$. For half-integer $\alpha$, termination can instead occur in the power-series factor of the exponent-one-half solution.

Given a bound $y$, a positive integer is $y$-smooth when all of its prime factors are at most $y$.

The space $[\mathbb{N}{]}^{\omega }$, also written ${\mathbb{N}}^{(\omega )}$, consists of all infinite subsets of the positive integers. An element is identified with its strictly increasing enumeration. If $s$ is finite, write $s⊏X$ when $s$ is the finite initial segment of this enumeration.

Take $X=\{0,1,2,\dots \}$, the nonnegative integers, and $Y=\{1,2,3,\dots \}$, the positive integers. Choose the injectionsHere $g$ is an inclusion map, while $f$ reaches only the positive even integers. In particular, $f$ is not a bijection: it misses every positive odd integer. Simply using the inverse function of $g$ on its image misses input zero.

The remedy is to follow the alternating injections starting at the missing input zero:The subscripts distinguish an input in $X$ from an output in $Y$, even when their numerical values agree. The resulting subset of $X$ is $A=\{0,2,6,14,30,\dots \}$. Its sequence of members satisfies $a_0=0$ and $a_{k+1}=2a_k+2$, giving $a_k=2^{k+1}-2$ by mathematical induction. Define the function

The image $h(A)=\{2,6,14,30,\dots \}=A\setminus \{0\}$ covers all the positive members of $A$ exactly once. The other inputs cover $Y\setminus A$ exactly once by staying fixed. These output sets are disjoint and their union is $Y$, proving that $h$ is a bijection. In particular, $h(0)=2$, $h(2)=6$, $h(6)=14$, while $h(1)=1$ and $h(4)=4$.

For completeness, its inverse function isThe familiar bijection $n\mapsto n+1$ also works, but this example shows something more specific: the two chosen injections can repair the missing zero by moving only a sparse sequence of inputs. The repair never has to shift the entire set.

A finite set $A$ of positive integers such that nonempty disjoint sets contained in $A$ have different sums, and the larger subset has the larger sum when their sizes differ. For $a_1<\cdots <a_n$, the size condition is equivalent to $a_1+\cdots +a_{k+1}>a_{n-k+1}+\cdots +a_n$ for $1\le k\le \lfloor (n-1)/2\rfloor$: the left side is the smallest possible sum of $k+1$ elements and the right side the largest sum of $k$ elements.

A positive integer $n$ is square-free when no square number greater than one is a divisor of $n$. It suffices to exclude squares of prime numbers; equivalently, every prime valuation is zero or one:Thus the prime factorization of a square-free integer is a product of distinct prime factors, with no repetitions. One is included: its prime factorization is an empty product and all its prime valuations are zero. These equivalent tests are stated in Grinberg's notes. ^[ref]

For signed integers, extend the definition by requiring $|n|$ to be a square-free integer, where $|n|$ denotes absolute value. Hence $-30$ and both $1,-1$ qualify. Zero does not: every prime number has its square as a divisor of zero. The Möbius function and radical of an integer below use their existing positive integer domains, so apply them to $|n|$ when handling a negative integer.

For example, $30=2\cdot 3\cdot 5$ is a square-free integer, whereas $12=2^2\cdot 3$ is not, because $4\mid 12$ and $v_2(12)=2$. Being a composite number causes no problem: $6,10,15$ are all square-free integers. A square-free integer need not be coprime to another integer: $6$ and $10$ are both square-free integers but have greatest common divisor two. In fact the only signed integers coprime to every integer are $1,-1$, since $\gcd (n,n)=|n|$.

For positive integers $a,b$, the useful product criterion isThe proof outline is just addition of prime valuations: $v_p(ab)=v_p(a)+v_p(b)$ can stay at most one only if neither input repeats a prime factor and no prime factor occurs in both. Thus $6\cdot 5=30$ is a square-free integer, but $6\cdot 10=60$ is not. An equivalent characterization is that every factorization $n=ab$ into positive integers has coprime factors. If $p^2\mid n$, the factorization $n=p(n/p)$ supplies two factors sharing $p$; conversely, a shared prime factor forces its square to divide $n$. For $30$, the unordered factor pairs $(1,30),(2,15),(3,10),(5,6)$ all have greatest common divisor one; for $12$, the pair $(2,6)$ fails.

Two existing arithmetic functions turn the definition into practical tests:The radical of an integer keeps one copy of each prime factor, so it changes precisely the integers with a repeated prime factor. Its definition is given in Evertse's exercise sheet. ^[ref] The Möbius function assigns $(-1{)}^r$ to a square-free integer with $r$ distinct prime factors and zero otherwise; squaring forgets the sign. Consequently ${\sum }_{n=1}^{60}\mu (n{)}^2=37$ counts exactly the green cells. This connects a restriction on repeated prime factors with weighted counting and inclusion-exclusion. ^[ref]

The squarefree part of a positive integer $n$ is the unique squarefree integer $s$ such that $n=s{t}^2$ for a positive integer $t$. For example, the squarefree part of $72=2^3{3}^2$ is $2$. It retains precisely the primes with odd prime exponents; the radical of an integer instead retains every distinct prime factor.

A square frame formed by removing a concentric square hole from a larger square. If outer and inner sides are positive integers $a>b$ with the same integer parity, the border has integer thickness $t=(a-b)/2$ and contains $a^2-b^2=4t(b+t)$ unit tiles.

The sum of squares of the first $n$ positive integers: $S_n={\sum }_{k=1}^n{k}^2=n(n+1)(2n+1)/6$. It counts a square-based stack with layers containing $1^2,2^2,\dots ,n^2$ objects. Differences $S_b-S_{a-1}$ give sums over consecutive squares.

The number of objects in a square-based pyramid with successive square layers of sizes $1^2,2^2,\dots ,n^2$. If $F(n)=n(n+1)(2n+1)/6$, direct algebra gives $F(n)-F(n-1)=n^2$ and $F(0)=0$. Mathematical induction therefore proves the displayed summation formula. Its leading term is $n^3/3$, so this sum grows cubically, even though its largest individual summand grows quadratically.

For $T(n)=1$ at $n\le 3$ and $T(n)=2T(\lfloor n/2\rfloor {)}^2$ otherwise, put $d=\max (0,\lfloor {\log }_{2}n\rfloor -1)$ for positive integer $n$. Taking logarithms gives $S(n)=1+2S(\lfloor n/2\rfloor )$, hence $S(n)=2^d-1$ and $T(n)=2^{2^d-1}$. These constant-value plateaux have exponential envelopes $2^{\Theta (n)}$, but do not justify $\Theta (2^{n/2})$ for all integer inputs.

Let E be the even positive integers, and take a finite-symmetric-difference parity colouring $\epsilon$ of $[E{]}^{\omega }$. The family $\{\{1\}\cup X:X\in [E{]}^{\omega },\epsilon (X)=0\}$ is Ramsey even under the every-ground-set convention, since every infinite ground set can be thinned to omit 1. It is not completely Ramsey: inside $[\{1\},E]$, every infinite tail has two subfamilies of opposite parity. Its supporting neighbourhood is closed and nowhere dense in the ordinary topology on infinite subsets, but open in the Ellentuck topology.

A positive integer whose adjacent decimal numerical digits differ by exactly 1. Its digits form a walk on the path graph $0-1-\cdots -9$, with a nonzero starting digit. Counting pandigital numbers of this type can use digit dynamic programming with the final digit and a bit mask of visited digits as the state.

For indexed occurrences with positive integer weights, let $D_i(t)$ record whether a subset of the first $i$ entries has sum $t$. The recurrence chooses whether the last occurrence is absent or present: $D_i(t)=D_{i-1}(t)\vee D_{i-1}(t-a_i)$, with an out-of-range term false. Initialize only sum zero true. Descending one-dimensional updates prevent reusing the current occurrence. Time is $O(ns)$ for target $s$ and space $O(s)$; positivity permits immediate rejection above the total. With weights bounded by $k$, the total is at most $nk$, making the bound polynomial in $n,k$.

The sum-of-divisors function adds all positive integer divisors of a positive integer, including the number itself:It is the divisor sum of the identity arithmetic function $\mathrm{id}(n)=n$, so $\sigma =\mathrm{id}\ast 1$ under Dirichlet convolution. Both factors are multiplicative functions, hence so is the sum-of-divisors function. The notation ${\sigma }_1$ distinguishes it from other weighted divisor sums. ^[ref]

For a prime number $p$ and a nonnegative exponent $a$, the positive integer divisors of the prime power $p^a$ are precisely $1,p,\dots ,p^a$. Their finite geometric series givesFor example, $\sigma (8)=1+2+4+8=15=(2^4-1)/(2-1)$. For a prime factorization $n={\prod }_{k=1}^r{p}_k^{a_k}$ with distinct prime numbers $p_k$ and positive exponents $a_k$, multiplicativity givesFor $n=1$, this is an empty product, equal to $1$. ^[ref]

The distributive property makes the formula especially beautiful: choosing one term from each factor produces each positive integer divisor exactly once, by the fundamental theorem of arithmetic. For $12=4\cdot 3=2^2\cdot 3$, the choices form a three-by-two grid with entries $2^i{3}^j$, where $0\le i\le 2$ and $0\le j\le 1$. Adding its rows givesThe divisor function counts six cells; the sum-of-divisors function adds their six values. Once the prime factorization is known, the product formula avoids testing every candidate integer divisor. Shared prime factors require care: $\sigma (4)=7\ne 9=\sigma (2{)}^2$, so the sum-of-divisors function is not a completely multiplicative function.

Subtracting the number itself gives the proper-divisor sum $s(n)=\sigma (n)-n$. Comparing $s(n)$ with $n$ distinguishes perfect numbers, deficient numbers, and abundant numbers. For $6$, $s(6)=1+2+3=6$; for $28$, $s(28)=1+2+4+7+14=28$. Both are perfect numbers. The calculation $s(8)=1+2+4=7<8$ makes $8$ a deficient number, while $s(12)=1+2+3+4+6=16>12$ makes $12$ an abundant number. These comparisons turn the sizes of integer divisors into a classification of positive integers. ^[ref]

This connection is ancient: Euclid's Elements, Book IX, Proposition 36, constructs a perfect number by multiplying the last term of $1,2,\dots ,2^{k-1}$ by their sum, when that sum is a prime number. In modern notation, put $q=2^k-1$ and $N=2^{k-1}q$, with $k\ge 2$ and $q$ a prime number. The sum-of-divisors function proves the construction immediately:Consequently the proper-divisor sum is $s(N)=N$. Taking $k=2,3$ produces the perfect numbers $6,28$. ^[ref]