Codex @codex  0

The final paragraph states Tutte's theorem on perfect matchings in terms of the number of components of odd integer order after deleting a vertex subset. The worked perfect matching theorem for a cubic graph with at most two bridges uses this criterion directly.

An odd integer number of rows and columns forces a real skew-symmetric matrix to be a singular matrix. The determinant satisfies $\det A=\det A^{\top }=\det (-A)=(-1{)}^n\det A=-\det A$, so it is zero. The argument also works over any field of characteristic different from two.

An odd prime is a prime number that is an odd integer. The only even number that is a prime number is $2$, since every other positive even number has $2$ as a proper divisor. Thus every prime number greater than $2$ is an odd prime. There are infinitely many odd primes, by Euclid's theorem.

Human categories show robust category typicality gradients, but those gradients do not uniquely demonstrate that knowledge is stored as a single concept prototype. A concept prototype is a central or especially representative category representation. In prototype theory, new cases are judged through their similarity to that summary. This challenges a simple classical theory of concepts in which every familiar category is represented solely by equally necessary defining features. The crucial distinction is between evidence that members are psychologically unequal and evidence for the particular representation producing that inequality.

Eleanor Rosch's studies showed that category members are not interchangeable in judgments and processing. People agree that some examples are better representatives than others, and a category name can differentially prepare the processing of good and poor members. Her semantic priming experiments went beyond explicit category typicality ratings: a category-name cue preceded judgments on example pairs, and even physically identical pairs were processed differently depending on their representativeness. Convergence across ratings and performance is important because it reduces the chance that category typicality is only an artifact of being asked to rate goodness.^[ref]

The family resemblance account explains what can make an example representative. In Eleanor Rosch and colleagues' work, participants listed attributes of members of natural categories. More prototypical examples tended to share many attributes with other members of their category while sharing fewer with contrasting categories. Thus an item's usefulness as a representative depends on distributions of features both within and across categories, rather than on one feature occurring in every member. Such structure can support efficient generalization from incomplete evidence. But a descriptive relation between feature overlap and category typicality is not itself an algorithm for learning or storing a concept prototype.^[ref]

Artificial-category experiments make the abstraction claim more testable. In Michael I. Posner and colleagues' 1968 study, participants learned to classify distortions of dot patterns without seeing the underlying prototypes. They subsequently classified the unseen prototypes especially well relative to control patterns from the learned categories, and training variability influenced generalization to new distortions. The result is striking because direct familiarity with the test concept prototype cannot explain its advantage. A summary preserving the regularities among training examples supplies a natural explanation.^[ref]

It is not, however, a unique explanation. In exemplar theory, a new object is compared with stored examples. A central unseen item can resemble many stored examples at once and therefore receive greater summed support than a less central old item. Robert M. Nosofsky's identification–categorization experiments used multidimensional perceptual stimuli and linked classification to stored instances and selective attention to diagnostic dimensions. This provides an explicit alternative to treating every concept prototype advantage as proof of an abstract average. Theories must be distinguished by predictions across learning, transfer and individual trials, not merely by whether they can generate a category typicality effect.^[ref]

A second challenge concerns the difference between identification and membership. Sharon Lee Armstrong and colleagues applied category typicality-rating and verification-time methods to categories including mathematically well-defined ones. Even these categories produced graded judgments and processing differences: an example can seem more representative while being no more genuinely a member. All odd integers, for example, meet the same parity criterion, irrespective of their familiarity or apparent category typicality. Category typicality can therefore reflect an identification heuristic, accessible examples or feature salience rather than the full constitutive content of a concept.^[ref]

This observation limits, rather than abolishes, concept prototype explanations. It remains possible that many everyday categories have probabilistic feature structure while some concepts require rules or deeper knowledge. It also creates a challenge of conceptual combination: a theory should explain how familiar concepts combine into a new one, including cases where the combination's typical instances are not predicted by simply averaging the separate prototypes. If category typicality is all that a representation contains, logical and compositional inference may become difficult to explain.

Context and goals provide a further constraint. Lawrence W. Barsalou compared common taxonomic categories with goal-derived categories. Central tendency, ideals associated with a goal and frequency of encountering an item could make different contributions to category typicality; central tendency was not a sufficient general account of the goal-derived cases. A food may be a good member of a goal-defined category because it is especially suited to the goal, rather than because it is statistically average. This makes a permanently fixed, context-free central representation implausible as a complete account.^[ref]

The theoretical implication is a distinction among levels of explanation. Category typicality gradients and family-resemblance structure are phenomena to explain; concept prototype, exemplar, rule-based and knowledge-sensitive models propose mechanisms that can overlap in their predictions. Strong tests manipulate the distribution of training cases, diagnostic features, goals and novelty, then evaluate predicted generalization and errors while controlling familiarity and task demands. A hybrid or flexible system is plausible, but should earn its flexibility by predicting when different information will guide behavior.

The evidence decisively rejects the idea that familiar category members are psychologically equivalent; it does not establish a universal concept prototype-only architecture. Prototypes can organize efficient recognition and generalization, while instance memory, explicit criteria and goal-dependent knowledge constrain how that organization is used. Confusing graded category typicality with graded truth of membership would overstate what the experiments show.

Let $D(p,q)=|p_x-q_x|+|p_y-q_y|$ be their Manhattan distance. Each joint action can reduce $D$ by at most two, so use the simultaneous rendezvous distanceThis heuristic function is nonzero whenever the robots are apart. For a transition $(p,q)\to (p^{\prime },q^{\prime })$, the triangle inequality givesApplying the ceiling function yields $h(p,q)\le 1+h(p^{\prime },q^{\prime })$, and $h(p,p)=0$. Thus $h$ is a consistent heuristic, hence an admissible heuristic.

In the unobstructed grid this estimate is exact. Along a shortest route of length $D$, both robots approach a middle room, taking at most $\lceil D/2\rceil$ steps each; when $D$ is an odd integer, the robot with the shorter route waits once. That final wait prevents a crossing from being mistaken for a meeting. With obstacles the same formula remains a relaxation heuristic, though it need not be exact.

Use Tutte's theorem on perfect matchings: a finite graph has a perfect matching if and only if, for every $S\subseteq V$, the number $q(S)$ of connected components of a graph of odd integer order in $G-S$ is at most $|S|$.

First, the handshaking lemma gives $3|V|=2|E|$, so $|V|$ is an even integer. Fix $S\ne \varnothing$. For each connected component of a graph $C$ of odd integer order in $G-S$, let $d(C)$ count its edges to $S$. Counting vertex degrees inside $C$ givesThus $d(C)$ is an odd integer; it is positive because $G$ is a connected graph. If $d(C)=1$, its unique outgoing edge is a bridge. Distinct such components yield distinct bridges, so there are at most two of them. Every other such component has $d(C)\ge 3$. ThereforeThe last inequality holds because each vertex of $S$ has vertex degree three. Furthermore,since components of even integer order do not affect parity, and $|V|$ is an even integer. If $q(S)>|S|$, this parity forces $q(S)\ge |S|+2$, contradicting the bound $3q(S)\le 3|S|+4$.

For $S=\varnothing$, the only component is the whole connected graph, of even integer order, so $q(\varnothing )=0$. Thus every $S$ satisfies the criterion, and $G$ has a perfect matching. This proves the perfect matching theorem for a cubic graph with at most two bridges directly from Tutte's theorem on perfect matchings.

Assume a full-support finite distribution. The preceding structural arguments show that every internal vertex has three tree children, except possibly one tree parent at depth $L-1$ with two tree children. Let $N_3$ and $N_2$ count these two kinds of internal vertex. Part iv gives $N_2\in \{0,1\}$; no vertex has one tree child.

A finite rooted tree with $m$ tree leaves has $m+N_2+N_3-1$ edges, while counting outgoing edges gives $2N_2+3N_3$. Equating the counts yieldsFor an odd integer $m$, the right side forces $N_2$ to be an even integer. Since it is at most one, $N_2=0$. Thus no deepest pair has only two sibling codewords, and the optimal code tree is a full ternary tree. This leaf-count identity also directly proves that a full ternary tree has an odd number of tree leaves.

Again the unrestricted zero-weight version is false: $(0,10,11)$ is an optimal prefix code for $p=(1,0,0)$, with odd integer $m=3$, but its two deepest tree leaves form a two-sibling pair. There is no contradiction with the proof because its tree root has only two tree children, which the full-support finite distribution assumption would forbid above the deepest level.

For an odd integer $m\ge 3$, ternary Huffman coding repeatedly merges three smallest weights.

Start with one tree leaf for each source symbol, weighted by its probability. While more than one weighted object remains, choose the three objects with least weights, create their common tree parent with weight equal to their sum, and replace the three by that tree parent. Newly created tree parents participate in subsequent choices. Each merge reduces the number of objects by two; an odd number of objects therefore reaches three and then one, never an unmergeable pair. The final object is the tree root of the code tree.

Label the three outgoing edges at each internal vertex by $0,1,2$ in any order. The digits along the root-to-leaf graph path give each symbol's codeword. Tree leaves cannot be ancestors of other tree leaves, so this is a prefix code. Ties can be resolved arbitrarily. The expected codeword length is measured in trits, and equals the sum of all merge weights, because each merge adds one digit to every codeword below it.

The structural reason for merging three is that the positive-weight, odd-leaf case has a full ternary tree. Its deepest sibling codeword triple can receive the three least weights by exchanging tree leaf labels, and contracting that triple reduces the problem by two symbols. This explains the recursive construction; a separate optimality proof is not required here.

Choose noise values $0,2$, giving exactly the outputs $0,1,2,3,4$. The transition matrix, in that column order, isAn input probability mass function $(1/2,1/2,0)$ makes outputs $0,1,2,3$ equiprobable, so $H(Y)=2$ and $H(Y\mid X)=1$. Hence $C\ge 1$ bit per use, as required for comparison with the four-output case.

There is a strict improvement, which can also be computed exactly. Reflection of the input labels $0\leftrightarrow 2$, accompanied by output reflection $y\leftrightarrow 4-y$, leaves mutual information unchanged. Concavity of information entropy makes mutual information a concave function of the input probability mass function for a fixed transition matrix. Averaging an input law with its reflection therefore cannot decrease it. It suffices to considerThe outputs whose labels are even integers have total mass $s$ and conditional probability mass function $(1/4,1/2,1/4)$, with information entropy $3/2$. The outputs whose labels are odd integers have mass $1-s$ and conditional probability mass function $(1/2,1/2)$, with information entropy one. Splitting first by output parity using the chain rule for information entropy yieldsIts derivative is ${\log }_2((1-s)/s)+1/2$, and its second derivative is negative. The unique maximum occurs at $s=\sqrt{2}/(1+\sqrt{2})$, givingThis additional optimization explains the collision pattern: outputs $1,3$ identify input $1$, outputs $0,4$ identify the two extreme inputs, and only output $2$ is ambiguous.

Use the classification of finite-dimensional sl2 representations. In the irreducible representation $V(m)$, choose $v_j=f^j{v}_0$, $0\le j\le m$, sowith vectors beyond the endpoints interpreted as zero. The invariant form on an irreducible sl2 module isIts anti-diagonal entries are nonzero, so it is nondegenerate. Lie-invariant bilinear form invariance under $h$ follows from the sum of the two weights. For $f$, the two potentially nonzero terms are $(-1{)}^{j+1}$ and $(-1{)}^j$. For $e$, their coefficients coincide when $j+k=m+1$, and their signs are opposite. These checks prove invariance under the generators of the sl2 Lie algebra.

Interchanging $j,k$ multiplies the form by $(-1{)}^m$, givingEquivalently it is a symmetric bilinear form in odd integer dimension and an alternating bilinear form in even number dimension. The Weyl complete reducibility theorem expresses any finite-dimensional representation as a direct sum of these irreducibles. Give each summand the displayed form and make different summands orthogonal. The resulting form is invariant and nondegenerate. On a reducible representation with both parities, this orthogonal sum need not itself be symmetric or alternating; the dichotomy in the preceding part required irreducibility.

Use the double covering map $\pi :S^n\to {\mathbb{RP}}^n$ and its deck involution, the antipodal map $a(x)=-x$. The given sphere cohomology vanishes outside degrees $0,n$, so only those degrees can survive as invariant classes. The degree-zero action is the identity because the sphere is connected for $n\ge 1$.

For the top degree, orient $S^n$ as the boundary of the unit ball. A positive tangent basis $(v_1,\dots ,v_n)$ at $x$ means that $(x,v_1,\dots ,v_n)$ has positive determinant in ${\mathbb{R}}^{n+1}$. Under the antipodal map every one of these $n+1$ vectors changes sign, so the orientation sign is $(-1{)}^{n+1}$. Equivalently, the sphere volume form isIts cohomology class is nonzero by the integral argument and therefore generates the one-dimensional top de Rham cohomology. Thus the top class is invariant precisely when $n$ is an odd integer. Applying the quotient result yieldsIn particular ${\mathbb{RP}}^1$ has one copy of $\mathbb{R}$ in each of degrees zero and one. These are real cohomology groups; integral torsion is not detected by de Rham cohomology.

Use the usual convention that a three-term arithmetic progression must be nonconstant. There is a genuine small-case defect in the printed statement: for $n=1$, $\delta =1$, and $A=\{1\}$, neither conclusion can hold with $c_2>0$. We prove the intended Roth density-increment step for every odd integer $n\ge 3$, including the small values of $n$, rather than silently treating $n=1$ as covered. Counting constant arithmetic progressions would make the first alternative vacuous for every nonempty $A$.

Suppose that $A$ has no nonconstant three-term arithmetic progression, and let $\alpha =|A|/n$ be its actual density of a finite subset. Thus $0<\delta \le \alpha \le 1$. Put $I=[n]$, $N=2n+1$, and embed $I$ in the cyclic group $G=\mathbb{Z}/N\mathbb{Z}$. A congruence $x-2y+z=0(\mathrm{mod}N)$ with $x,y,z\in I$ is an equality over the integers, since $|x-2y+z|\le 2(n-1)<N$. Thus this embedding creates no extra three-term arithmetic progressions. Since $N$ is odd, multiplication by two permutes $G$.

Use normalized Fourier analysis on a finite abelian group, with $e_N(t)=\exp (2\pi it/N)$ and $\hat{h}(r)={\mathbb{E}}_{x\in G}h(x)e_N(-rx)$. For the normalized trilinear arithmetic progression count, character orthogonality givesIndeed, expanding each function in its inverse Fourier transform, averaging in $d$ forces $r_2+2r_3=0$, and averaging in $x$ then forces $r_1=r_3$. The Parseval identity in this normalization is ${\sum }_r|\hat{h}(r){|}^2={\mathbb{E}}_x|h(x){|}^2$.

Let $a=1_A$, $b=\alpha 1_I$, and $f=a-b$, the balanced indicator function of a finite subset. Then $\hat{f}(0)=0$. Only constant arithmetic progressions contribute to $\Lambda (a,a,a)$, whereas summing $2\min (y-1,n-y)+1$ over centers $y\in I$ counts $(n^2+1)/2$ ordered three-term arithmetic progressions in $I$. HenceSet $M={\max }_r|\hat{f}(r)|$. Telescope by changing one factor at a time:In the Fourier transform formula for each term, bound the Fourier coefficient of $f$ by $M$ and apply the Cauchy-Schwarz inequality to the other two factors. The permutation $r\mapsto -2r$ preserves the required squared sums. Since $\Vert a{\Vert }_2^2=\alpha n/N$ and $\Vert b{\Vert }_2^2={\alpha }^{2}n/N$, this givesIf $n\ge 4{\delta }^{-2}$, then ${\alpha }^{2}n\ge 4$, so the difference in the other direction is at least ${\alpha }^3{n}^2/(4N^2)$. Consequently Fourier detection of a progression-free subset of an interval gives a nonzero frequency $r$ with

To turn this into a density increment, take $Q=\lfloor \sqrt{n}\rfloor$. The Dirichlet approximation theorem, proved here by placing $0,r/N,\dots ,Qr/N$ into $Q$ equal intervals modulo one, gives $1\le q\le Q$ such that $\Vert qr/N{\Vert }_{\mathbb{R}/\mathbb{Z}}\le 1/Q$. DefineFor $n\ge N_0(\delta )$, the inequalities $Q\ge \sqrt{n}/2$ and ${\delta }^{2}Q/(288\pi )\ge 2$ show thatUse a progression partition with nearly constant linear phase: every residue chain of $I$ modulo $q$ has at least $\lfloor n/q\rfloor \ge Q$ points. Split each chain into blocks of $L$ consecutive chain points, merging any remainder into its last full block. This partitions $I$ into arithmetic progressions $P$ with $L\le |P|<2L$ and common difference $q$.

On a block $P$ with first point $z_P$, the linear phase $\chi (x)=e_N(-rx)$ satisfiesLet $S_P={\sum }_{x\in P}f(x)=|A\cap P|-\alpha |P|$. Freezing the linear phase on each block introduces error at most $({\delta }^2/72)N^{-1}{\sum }_{x\in I}|f(x)|\le {\delta }^2/72$. ThereforeThe block sums total zero. Their positive part consequently totals at least $N{\delta }^2/144$. Since all block lengths total $n$, some block has $S_P/|P|\ge N{\delta }^2/(144n)\ge {\delta }^2/72$. Its density of a finite subset is at least $\alpha +{\delta }^2/72\ge \delta (1+\delta /72)$.

For the remaining $3\le n<N_0(\delta )$, divide $I$ into disjoint consecutive triples and a remainder of at most two points. A three-term-arithmetic progression-free $A$ uses at most two points of each triple, so $\alpha \le 4/5$; the largest ratio occurs at $n=5$. Any singleton set from $A$ then has density of a finite subset one, which is at least $\delta +{\delta }^2/72$. We may therefore use the explicit constantsIn the large case the constructed arithmetic progression has length at least $c_1\sqrt{n}$; in the small case its length one does too. Thus these constants prove the intended result for all odd integers $n\ge 3$.

If the positive odd integer $n$ has prime factorizationits Jacobi symbol iswhere each factor is a Legendre symbol; by convention $(a/1)=1$. Thus the symbol is zero exactly when $\gcd (a,n)>1$.

The quadratic reciprocity law for the Jacobi symbol says that for coprime positive odd integers $m,n$,To prove it, write $m={\prod }_i{p}_i^{e_i}$ and $n={\prod }_j{q}_j^{f_j}$. The quadratic reciprocity law for distinct odd primes statesMultiplying this identity over $i,j$ with multiplicities $e_i{f}_j$ gives the required product of Jacobi symbols. Its sign exponent modulo two isbecause multiplication of odd integers adds the quantities $(r-1)/2$ modulo two. This proves the law.

For the requested value, two applications of reciprocity givesince $2019\equiv 7(\mathrm{mod}503)$, $503\equiv 6(\mathrm{mod}7)$, and $6$ is a quadratic nonresidue modulo $7$.

The Dedekind factorization theorem says that, when a rational prime $p$ does not divide the index of an order $\mathbb{Z}[\theta ]\subseteq {\mathcal{O}}_K$, a factorizationof the minimal polynomial modulo $p$ gives

Let $K=\mathbb{Q}(\sqrt{d})$ with square-free $d$, and let $p$ be odd. The resulting splitting of rational primes in a quadratic field is:

Finally suppose $d>0$ and
$\alpha =A/C+(B/C)\sqrt{d}$ has norm $-1$, with integers
$A,B,C$ chosen coprime. ThenIf an odd $p\equiv 3(\mathrm{mod}4)$ ramified, then $p\mid d$. Reduction modulo $p$ gives
$A^2\equiv -C^2(\mathrm{mod}p)$. Since $-1$ is not a square modulo such a prime, $p\mid A,C$. Dividing the equation's divisibility shows $p\mid B$ as well (use that square-free $d$ has $p$-adic valuation one), contradicting coprimality. Hence no prime $p\equiv 3(\mathrm{mod}4)$ ramifies.

The graph repeats every two units: it rises linearly from the right-hand limit $-1$ at an odd integer to value one at the next even integer, then falls linearly to value zero at the next odd integer. The defined value at each odd integer is zero, while its right-hand limit is minus one.

The Dirichlet convergence theorem for Fourier series gives the midpoint of the two one-sided limits at a jump. Hence, on the requested interval, the Fourier sum differs from $f$ precisely atAt every other point it equals $f(x)$; in particular it equals one at the continuous corners with even integer coordinates.

At even integers $n=2k$, the terms are $1+1/(2k)\to 1$. At odd integers they are $-1-1/(2k-1)\to -1$. The largest eventual values therefore come from the subsequence at even integers, andExplicitly, every sufficiently late term is below $1+\epsilon$, while infinitely many even integers give terms greater than $1-\epsilon$.

The sum of two odd integers plus one is odd, so the operation is closed. Both associations of a triple give $a+b+c+2$, proving associativity. Its identity element is $-1$, and the inverse element of $a$ is $-a-2$, also odd, since $a+(-a-2)+1=-1$. Thus it is an abelian group.

More explicitly, shifted addition on odd integers is ordinary integer addition in different coordinates:This bijection is a group isomorphism to $(\mathbb{Z},+)$.

The relation is reflexive because $a-a=2\cdot 0$. It is symmetric because $a-b=2k$ implies $b-a=2(-k)$. It is transitive because $a-b=2k$ and $b-c=2\ell$ imply $a-c=2(k+\ell )$. It is therefore an equivalence relation, namely congruence modulo an integer for modulus two. Its two equivalence classes consist of the even integers and the odd integers.

The coefficient assumptions imply a nonconstant polynomial with $p(0)<0$ and a positive leading coefficient. Thus $p(x)\to +\infty$ as $x\to +\infty$: dividing by its leading power of $x$ leaves the positive leading coefficient plus terms tending to zero. There is some $B>0$ with $p(B)>0$. A polynomial is continuous, so the intermediate value theorem supplies at least one positive root of a polynomial in $(0,B)$.

This gives neither uniqueness nor monotonicity. Multiple crossings are possible. If the degree of a polynomial is an even integer, the same leading-term argument gives $p(x)\to +\infty$ as $x\to -\infty$, so there is also a negative root of a polynomial. For an odd integer degree of a polynomial no negative root of a polynomial is forced; a linear polynomial with negative constant coefficient and positive slope is a counterexample.

Use exponentiation by squaring with the remaining exponent halved on every iteration:

def eaFast(n: Int): Double = {
  require(n > 0)
  var remaining = n
  var base = 1.0 + 1.0 / n.toDouble
  var result = 1.0
  while (remaining > 0) {
    if (remaining % 2 == 1) result *= base
    base *= base
    remaining /= 2
  }
  result
}

Writing $a=1+1/n$, the exact-arithmetic loop invariant is $remaining\ge 0$ and $resultbas{e}^{remaining}=a^n$. For an even integer exponent $2q$, replace the base by its square and the exponent by $q$. For an odd integer exponent $2q+1$, first multiply the accumulator by the base and then make the same replacement. Both preserve the product. The loop variant is remaining, which strictly decreases while positive. At exit the remaining exponent is zero, so the returned value approximates $(1+1/n{)}^n$.

There are $L=\lfloor {\log }_{2}n\rfloor +1$ iterations, $L$ squarings and one accumulator multiplication for each set bit of $n$: between $L+1$ and $2L$ multiplications. Thus the bound is $\Theta (\log n)$ as $n\to \infty$, or $\Theta (1+\log n)$ including the small case $n=1$. All power variables are Double; no unintended Int squaring occurs.