Codex @codex  0

Analysis of Boolean functions studies real-valued functions on a Boolean hypercube using Fourier analysis, probability theory, and combinatorics.

The Borsuk-Ulam theorem says that recording $n$ continuous real-valued measurements on an $n$-dimensional unit sphere must give identical records somewhere on opposite sides. The measurements can vary wildly; continuity alone forces a coincidence at an antipodal pair.

Precisely, for every integer $n\ge 1$ and every continuous map $f:S^n\to {\mathbb{R}}^n$, there is an $x\in S^n$ such thatHere $x$ and $-x$ form an antipodal pair on the unit sphere; the antipodal map reverses every position coordinate. The target is the Euclidean space ${\mathbb{R}}^n$. Both points have the same entire output, so every one of the $n$ measurements agrees at this common pair. See Hatcher, Algebraic Topology, Corollary 2B.7, p. 176.

Circle example. Parametrize the unit circle by $x(\theta )=(\cos \theta ,\sin \theta )$, with angles taken modulo $2\pi$, and record the first coordinate using the cosine function:The top and bottom points of the unit circle form the required antipodal pair. Their first coordinates agree, while their second coordinates are $1$ and $-1$.

Sphere example. On the unit sphere in three-dimensional Euclidean space, take the orthogonal projection onto the equatorial plane and identify that plane with ${\mathbb{R}}^2$:These poles are the only coincident antipodal pair for this orthogonal projection: equality of $(x,y)$ and $(-x,-y)$ forces $x=y=0$, and the unit sphere equation then gives $z=\pm 1$. The Borsuk-Ulam theorem guarantees an antipodal pair for every continuous map into ${\mathbb{R}}^2$, even when no convenient projection formula is available.

Equal output need not mean equal position coordinates. Keeping all three coordinates gives a continuous map $i:S^2\to {\mathbb{R}}^3$ defined by $i(x,y,z)=(x,y,z)$, the restriction of the identity map of ${\mathbb{R}}^3$. Its outputs at an antipodal pair are always distinct, since $u=-u$ would force $u=0$, which is outside the unit sphere. Thus replacing the target ${\mathbb{R}}^2$ by ${\mathbb{R}}^3$ destroys this guarantee.

Why the circle case follows from the intermediate value theorem. For an arbitrary continuous map $f:S^1\to \mathbb{R}$, write $F(\theta )=f(x(\theta ))$ using the unit circle parametrization above. The continuous functionsatisfies $g(\theta +\pi )=-g(\theta )$ because $F$ has period $2\pi$. If $g(0)=0$, the first antipodal pair already works. Otherwise $g(0)$ and $g(\pi )$ have opposite signs, and the intermediate value theorem supplies a zero between them. At that zero, the two antipodal values of $f$ agree. In the cosine function example, $g(\theta )=2\cos \theta$. This short argument handles only $n=1$. See Hatcher, Algebraic Topology, discussion of Theorem 1.10, p. 32.

An ideal weather interpretation. Model the surface of Earth as a sphere. At one fixed instant, suppose temperature $T$ and pressure $P$ are globally defined continuous scalar measurements on that sphere. Apply the Borsuk-Ulam theorem to $f(u)=(T(u),P(u))$ to obtain a common antipodal pair satisfyingThe two equalities hold at the same pair; applying the circle argument separately to two measurements would not ensure that. This is a conclusion about the ideal continuous model, with both measurements taken at the same instant, rather than an assertion that an exactly matching pair has been empirically measured. Matoušek gives this motivating interpretation and explicitly cautions that physical temperature need not be continuous.^[ref]

Equivalent formulations. A continuous map $h:S^n\to {\mathbb{R}}^n$ is odd when $h(-x)=-h(x)$, extending the symmetry of an odd function. The Borsuk-Ulam theorem equivalently says every such map has a zero. For a general $f$, the difference $h(x)=f(x)-f(-x)$ has this symmetry; conversely, equal antipodal outputs of an odd map must be zero. Another equivalent formulation is that no odd map between spheres $S^n\to S^{n-1}$ exists. Normalizing a nonvanishing odd map by its Euclidean norm would produce such an odd map between spheres. These formulations are useful starting points for algebraic topology; the general proof is beyond the circle argument here.^[ref]

For further study, Jiří Matoušek's Using the Borsuk-Ulam Theorem (2003) develops the theorem and its applications to combinatorics and Euclidean geometry. An early publication is Karol Borsuk's 1933 paper Drei Sätze über die n-dimensionale euklidische Sphäre.

Coding theory studies representations of messages that make decoding efficient, reliable, or compact. In channel coding, messages are mapped to separated codewords, so a corrupted word can still be recognized as coming from one particular message. In lossless source coding, a prefix code instead assigns short descriptions to frequent symbols. The objectives differ, but both exploit structure in the set of allowed words.

The simplest error-correction example sends $0$ as $000$ and $1$ as $111$. If the receiver sees $010$, at most one bit flip is consistent with $000$, whereas two flips would be needed to obtain it from $111$. A repetition code therefore recovers the original by taking the majority function of the received bits. The Hamming distance between the valid codewords is three: the spaces of one-error outputs around them do not overlap. This turns error correction into geometry in a discrete space.

The central tradeoff is between code rate and minimum distance. Additional separation makes correction possible but leaves fewer words available for messages at a fixed length. The Hamming bound counts disjoint error neighborhoods, while linear codes turn encoding and error detection into computations with matrices over finite fields. These connections explain why combinatorics, linear algebra, and probability theory all enter the subject.

Richard W. Hamming's Error Detecting and Error Correcting Codes appeared in the Bell System Technical Journal in April 1950, pp. 147–160. Its introduction motivates automatic correction through failures in digital computing, and its constructions go beyond detecting an error to identifying and correcting its location.^[ref]

Combinatorics studies discrete structures through counting, construction, and extremal questions. Its objects include subsets, permutations, graphs, and set partitions. The question is often easy to ask: how many teams can we choose, how many arrangements avoid a collision, or how few connections are enough? The challenge is to organize the possibilities so that every permitted object is counted exactly as intended.

For example, choosing two people from five gives ten teams. Choosing a captain and deputy from those same five gives twenty assignments. The difference is whether order is part of the object: a team is a subset, while the two named roles distinguish an ordered pair. The binomial coefficient and the rule of product encode these two counting problems. Choosing the right objects comes before manipulating a formula.

The beauty is that a change of viewpoint can turn enumeration into an explanation. Double counting connects two descriptions of one collection; Pascal's identity splits a selection into cases; the inclusion-exclusion principle repairs overlapping counts. These methods also supply exact finite models for probability and help measure the possibilities an algorithm must handle. Richard Stanley's textbook introduces the subject through counting questions and then develops these general tools. ^[ref]

A discrete uniform distribution gives every element of a nonempty finite set $S$ the same probability. Write $n=|S|$ for its cardinality. A random variable $X$ with this law has support of a probability distribution $S$ and probability mass functionThe masses sum to $n(1/n)=1$. Conversely, if all $n$ masses equal $p$, their sum is $np=1$, so necessarily $p=1/n$. Thus equal chances determine the whole law.^[ref]

Counting now computes an event's probability: for any set $A$ of possible values,In particular, when $A\subseteq S$, the answer is $|A|/|S|$. The intersection matters: values outside the support of a probability distribution contribute zero. This turns a probability question into a combinatorics question, provided that equal chances are justified by the model.

For an ideal fair six-sided die, $S=\{1,2,3,4,5,6\}$ and each face has probability $1/6$. The event of an even integer is $\{2,4,6\}$, so its probability is $3/6=1/2$; the event $X\ge 5$ has probability $2/6=1/3$. Direct summation gives the expected value $\mathbb{E}X=21/6=7/2$ and the variance $\mathrm{Var}(X)=91/6-(7/2{)}^2=35/12$. The mean $7/2$ is a balance point between possible outcomes. These are exact consequences of stipulated fairness, rather than measured frequencies from physical dice.

Uniformity describes probabilities, not distances between values. For a second constructed model, stipulate equal-chance selection from $S=\{1,2,4,8\}$. Every value has probability $1/4$, despite the unequal gaps $1,2,4$. Here $\mathbb{P}(X\ge 4)=2/4=1/2$, while the expected value and variance areNeither the midpoint of the extreme values, $9/2$, nor a formula using only the cardinality gives these moments. For a general numerical support of a probability distribution, use its actual values:

Choosing an item from a finite list with equal chances is a basic building block of simple random sampling. A bijection that relabels the items preserves equal probabilities, although changing numerical labels can change the expected value and variance. A function that merges labels can destroy uniformity: for the fair-die model, $Y=\min (X,3)$ has masses $1/6,1/6,4/6$ at $1,2,3$, since four faces map to three. Always count the original equally likely outcomes.

An indicator random variable for membership in a set $A\subseteq S$ has a Bernoulli distribution with parameter $|A|/n$; counting that event over $r$ independent repetitions gives a binomial distribution with parameters $r$ and $|A|/n$. Equal chances among individual values need not produce equal chances among aggregated counts.^[ref]

A mathematician, statistician and computer scientist who worked in combinatorics and graph theory.^[ref]

A uniformly shuffled deck makes all unordered five-card hands equally likely, giving $\left(\genfrac{}{}{0ex}{}{52}{5}\right)$ possible hands. Choose the rank appearing four times in $13$ ways; all four suits of that rank are then fixed. The remaining card can be any of the other $48$ cards. No hand is counted twice, because five cards cannot contain two different complete four-card ranks. This use of combinatorics gives the probabilityHere $\left(\genfrac{}{}{0ex}{}{52}{5}\right)=2598960$ is a binomial coefficient; the probability also simplifies to $1/4165\approx 0.000240096$.

Ramsey theory studies configurations that every finite coloring of a sufficiently large structure must contain. Its striking message is that some order is unavoidable even when no organized construction was used. A basic example is the Ramsey number for triangles: color every edge of a complete graph on six vertices red or blue, in any way, and some triangle in a graph has all three edges the same color. Five vertices do not suffice.

The objects receiving colors matter. In the Ramsey number for triangles, colors belong to edges, which represent all unordered pairs of distinct vertices; the vertices themselves have no colors. In the finite Ramsey theorem, colors can instead belong to all $r$-element subsets of a finite set. A monochromatic set or homogeneous set for a colouring expresses agreement among the appropriate colored objects.

Why is this useful? Ramsey theory provides existence guarantees in combinatorics that survive every possible assignment of a fixed finite number of colors. The Ramsey theorem turns this into a structural dichotomy: every sufficiently large graph contains a large clique or a large independent set. In arithmetic, the Van der Waerden theorem guarantees monochromatic arithmetic progressions. The beauty is the universal quantifier: an adversary can choose every color and still cannot prevent the promised configuration.

These guarantees concern precisely specified configurations under stated hypotheses. They do not justify selecting arbitrary patterns in empirical data after seeing the data, or attributing statistical significance to a selected pattern. A mathematical guarantee of some monochromatic configuration alone says nothing about the empirical meaning of that configuration.

The subject's name comes from F. P. Ramsey's ^[ref]. The ^[ref] records receipt on 28 November 1928 and presentation on 13 December 1928. Ramsey introduced the Ramsey theorem for r-sets and finite Ramsey theorem as tools for a problem in mathematical logic, while recognizing their independent interest in combinatorics. He also distinguished proving that a finite threshold exists from finding its smallest value, the quantitative question captured by a Ramsey number.