Codex @codex  0

Online text: pages.cs.wisc.edu/~remzi/OSTEP/threads-bugs.pdf

Cited passages: Chapter 32, section 32.3, Prevention: Circular Wait, printed pp. 7–8: consistent acquisition ordering and hidden calls; Operating Systems: Three Easy Pieces, chapter 32, section 32.3, printed pp. 5–7, figures 32.6–32.7: opposing acquisition orders and circular wait.

Online text: pages.cs.wisc.edu/~remzi/OSTEP/threads-locks.pdf

Cited passages: Chapter 28, sections 28.1–28.2 and 28.7–28.8: ownership, multiple lock objects, and spinning; Chapter 28, sections 28.6–28.7, figures 28.1–28.3: separate test/set failure and indivisible exchange; Chapter 28, sections 28.7–28.8, printed pp. 8–9: preemption requirement and lack of fairness guarantees; Operating Systems: Three Easy Pieces, chapter 28, sections 28.1–28.2, printed pp. 1–2: lock ownership and critical sections.

Online text: pages.cs.wisc.edu/~remzi/OSTEP/vm-complete.pdf

Cited passages: Chapter 23, section 23.1, printed pp. 7–8: a subsequent exec can discard most of the inherited address space; Operating Systems: Three Easy Pieces, chapter 23, section 23.1, Other Neat Tricks, printed pp. 7–8: protected sharing, copying on a write, and fork/exec motivation.

Online text: opendatastructures.org/ods-python/11_2_Counting_Sort_Radix_So.html

Cited passages: Open Data Structures, section 11.2.1: associated data, backwards placement, Theorem 11.7 and stability; Open Data Structures, section 11.2.2: least-significant-digit passes, stability argument, and Theorem 11.8.

Online text: opendatastructures.org/ods-python/11_1_Comparison_Based_Sorti.html

Cited passages: Open Data Structures, section 11.1.4, Theorem 11.5: deterministic comparison-tree lower bound.

Online text: opendatastructures.org/ods-python/5_1_ChainedHashTable_Hashin.html

Cited passages: Open Data Structures, section 5.1, the array of lists and the find/remove operations.

Additional cited passages: §5.1.1, multiplicative hashing construction and Lemma 5.1; indicator-variable proof of Lemma 5.2. The online Python section is undated; the parent record dates the print book.

A one-way permutation is a bijective one-way function on its input domain. Injectivity is useful for binding in bit commitment, because an output has only one possible preimage even if a dishonest sender has unlimited computation.

A class specifies a kind of object in a class-based object system, commonly declaring fields, methods and construction rules. An instance has its own identity and state, while class-level members can be shared. A Point class might store two coordinates and provide a distance method; two instances with equal coordinates can still be distinct objects. A class is related to a type but not identical to every notion of type: languages vary in nominal typing, structural interfaces and metaclass rules. A subclass must respect the behavioural promises expected by users of its base interface.

// Target: computer-science.bigb

In object-oriented programming, encapsulation packages an object's state with the operations that act on it and can restrict direct access to its implementation. It is the object-oriented use of encapsulation.

By David Bindel.

Online text: www.cs.cornell.edu/courses/cs4220/2022sp/lec/2022-03-07.pdf

Cited passages: Changing shifts, §3, PDF p. 3: approximate eigenvector equation and Rayleigh quotient; Power iteration, §1, PDF pp. 1–2: diagonalizable expansion and nonzero first coordinate of the starting vector.

For positive integers $k,n$, Jordan's totient function $J_k(n)$ counts tuples $(a_1,\dots ,a_k)$ of residue classes modulo $n$ for which $\gcd (a_1,\dots ,a_k,n)=1$. The coordinates together must avoid a common prime divisor of $n$; they need not each be units.

For each prime factor $p$ of $n$, exactly $(n/p{)}^k$ tuples have all coordinates divisible by $p$. The inclusion-exclusion principle, applied to simultaneous divisibility by the distinct prime factors, therefore givesIn particular $J_1(n)=\phi (n)$ is Euler's totient function. For $k=2,n=6$, the formula gives $J_2(6)=36(1-1/4)(1-1/9)=24$. The pair $(2,3)$ is counted because $\gcd (2,3,6)=1$, even though neither coordinate is coprime to six.

If a prime number $p$ divides a product $ab$ of integers $a,b$, then $p$ divides $a$ or $b$ (possibly both):For example, $5\mid 6\cdot 10$ and $5\mid 10$. The hypothesis that $p$ is a prime number matters: $6\mid 2\cdot 3$, although six divides neither factor. When $p$ does not divide $a$, the greatest common divisor of $p$ and $a$ is one; multiply Bézout's identity $up+va=1$ by $b$ to see that $p\mid b$. Repeated application makes this the uniqueness step in the fundamental theorem of arithmetic. ^[ref].

For a completely computed example, $7\mid 20\cdot 21$ because $20\cdot 21=420=7\cdot 60$, while $20=7\cdot 2+6$ shows that seven does not divide twenty. Bézout's identity $3\cdot 7-20=1$ becomes, after multiplication by $21$,The two terms on the right are divisible by seven, which explicitly recovers the forced divisibility of the second factor. Both alternatives can hold: $7\mid 14\cdot 21$, and seven divides both $14$ and $21$.

In fact the property characterizes prime numbers among the integers greater than one. If $c$ is a composite number, choose $c=ab$ with $1<a,b<c$; then $c\mid ab$, but $c$ divides neither $a$ nor $b$. For several factors, repeated application of Euclid's lemma says that a prime number dividing their product divides at least one factor. In a product of prime numbers, that factor must equal it, because a prime number has no other prime factor. This is what prevents a different collection of prime factors from representing the same positive integer in the fundamental theorem of arithmetic.

Book VII, Proposition 30 of Euclid's Elements states the result in terms of a prime number measuring a product; its proof uses coprimality and ratios. The calculation using Bézout's identity above is a modern way to explain the same divisibility statement. ^[ref]

For an integer modulus $N\ge 2$, a primitive root is a unit $g$ whose multiplicative order is $\phi (N)$. Its powers enumerate the entire unit group $U(N)$, so a primitive root exists exactly when this group is a cyclic group.

Modulo seven, successive powers of three give $3,2,6,4,5,1$, reaching all six units. The element two instead has powers $2,4,1$ and multiplicative order three, so it is not a primitive root.^[ref]

Existence depends on $N$. Modulo eight, every unit is represented by an odd integer and has square one, since $(2k+1{)}^2-1=4k(k+1)$ is divisible by eight. No such element can generate a group of four units. The exact possible moduli are listed by the primitive-root modulus classification.

Every nonnegative integer is a sum of squares with four terms, with zero terms allowed. Precisely, for every integer $n\ge 0$, there exist nonnegative integers $a,b,c,d$ such thatAllowing arbitrary integer roots gives the same statement: changing a root to its absolute value leaves the resulting square number unchanged. Four is a uniform upper bound on the number of nonzero terms, rather than a demand for four positive terms. Repeated square numbers are allowed. Conrad states the positive case and explicitly explains the role of zero terms; $n=0$ follows by taking all four roots zero. ^[ref]

The small cases make the convention visible:In particular, $1$ could not be a sum of squares with four strictly positive roots, since each term would be at least one. Geometrically, a square of integer side length $a$ has area $a^2$: the theorem says that any nonnegative whole-number total area can be split into at most four such square areas. It does not assert that those squares tile one larger square or a prescribed rectangle.

Why does the fourth term matter? Two square numbers do not suffice for $3$: in modular arithmetic, a square number has remainder zero or one modulo four, so their sum cannot be three modulo four. The sum of two squares theorem gives a complete criterion for the positive integers representable with two terms. Even three terms leave gaps. A square number has remainder $0,1,$ or $4$ modulo eight; adding three of these, with repetition allowed, never gives seven modulo eight. Thus $7,15,23,31,\dots$ cannot be sums of three square numbers, although Lagrange's four-square theorem represents all of them with four. This also proves that the bound four cannot be reduced to three.

The modulo-eight obstruction is not the only way that three terms can fail. For example, $28$ needs four: if three square numbers added to $28$, their remainders modulo four would force all three roots even. Dividing by four would then express $7$ as a sum of three square numbers, contradicting the preceding calculation. These short checks explain the examples without requiring a full classification of sums of three square numbers.

The practical benefit of Lagrange's four-square theorem is an existence guarantee for a family of Diophantine equations: for every nonnegative integer $n$, the displayed equation has an integer solution. It does not specify a unique solution. For instance, $65=8^2+1^2+0^2+0^2=7^2+4^2+0^2+0^2=6^2+4^2+3^2+2^2$. To find a representation by a finite search, enumerate $0\le d\le c\le b\le a\le \lfloor \sqrt{n}\rfloor$ and test the sum. The floor function supplies a finite bound because no single term can exceed $n$, and sorting roots removes duplicate orderings without discarding any possible sum. The theorem guarantees that the search succeeds.

A greedy algorithm that repeatedly subtracts the largest available square number need not find four terms: for $23$ it chooses $16+4+1+1+1$, while $23=9+9+4+1$ uses four. The appeal of the theorem is this gap between local choices and a global promise: individual square numbers become farther apart, and two or three terms leave arithmetic obstructions, yet four terms cover every nonnegative integer.

For historical orientation, Conrad dates Lagrange's four-square theorem to $1770$ and identifies the memoir as Démonstration d'un théorème d'arithmétique: it appeared in the Berlin Academy's volume for the year $1770$, published in $1772$, pages $123$–$133$. Keeping the volume year and publication year distinct avoids an apparent conflict between dates. ^[ref]

The Erdős-Turán inequality bounds how unevenly finitely many points fill the half-open interval $[0,1)$ by measuring finitely many Fourier modes. For $x_1,\dots ,x_N\in [0,1)$ define their normalized star discrepancy byThere is a universal constant $C$ such that, for every positive integer $H$,The finite-point form follows from the corresponding probability measure inequality by placing mass $1/N$ at each point of the unit circle represented by $x_n$.^[ref]

The cutoff $H$ trades an approximation error against the measured exponential sums. If each fixed nonzero Fourier mode tends to zero as $N$ grows, take the limit superior first with $H$ fixed, then let $H$ grow. This gives $D_N^{\ast }\to 0$, the quantitative route to equidistribution.

For the grid $x_n=(n-1)/N$ with $N\ge 2$, every displayed exponential sum vanishes for $1\le h<N$ by the finite geometric series. Choosing $H=N-1$ yields $D_N^{\ast }\le C/(N-1)$; direct counting gives the sharper exact value $1/N$.