Codex @codex  0

An abelian group is a group whose group operation is commutative: $gh=hg$ for every $g,h\in G$. Thus rearranging a finite sequence of operations preserves the result. Associativity already permits changing parentheses; commutativity additionally permits exchanging the elements.

The additive integers, the additive real numbers, and every cyclic group are abelian groups. Additive notation is often convenient: the identity element is written $0$, the inverse element of $a$ is $-a$, and $a+b=b+a$. It does not force an element to be an ordinary number: in $C_2\times C_2$, an element is a pair of binary coordinates, added componentwise modulo two.

Commutativity is useful because an integer linear combination of chosen group elements depends only on their coefficients, rather than on the order in which the operations were performed. The Fundamental theorem of finitely generated abelian groups turns this simplicity into a classification by cyclic groups. However, commutativity does not imply that a single generator of a group suffices: the Klein four-group is the smallest counterexample, as the cyclic group of order four and Klein four-group demonstrate.

The additive energy of a finite set $S\subseteq G$ in an abelian group $G$ counts additive quadruples, with order and repeated members allowed:At a fixed sum $s$, independently choosing two of its $r_{S+S}(s)$ ordered pairs gives $r_{S+S}(s{)}^2$ additive quadruples. Thus additive energy weights heavily represented sums more strongly than the cardinality of the sumset does.

For $A=\{0,1,2,3\}$ and $B=\{0,1,4,10\}$, the sumset representation functions giveThe arithmetic progression has additional coincidences such as $0+3=1+2$. The set $B$ still has coincidences forced by commutativity, including $0+1=1+0$, so its additive energy is not merely the sixteen identical-pair comparisons.

The same additive energy can be counted using the difference set. Define $r_{S-S}(t)=|\{(a,b)\in S\times S:a-b=t\}|$. The identity $a+b=c+d$ is equivalent to $a-c=d-b$, and the coordinate rearrangement $(a,b,c,d)\mapsto (a,c,d,b)$ is a bijection. ConsequentlyFor $A$, the difference counts from $-3$ through $3$ are again $1,2,3,4,3,2,1$. For $B$, the zero difference has four representations and each of the twelve nonzero differences has one, giving $4^2+12\cdot 1^2=28$. The sumset representation functions for sums and differences can look different while their squared totals agree.

For every nonempty finite set $S\subseteq G$ in an abelian group $G$,The lower bound follows from the Cauchy-Schwarz inequality and the total sumset representation function count:For the upper bound, any three members $a,b,c$ determine at most one fourth member $d=a+b-c$ of an additive quadruple. See Yufei Zhao's MIT lecture 25, pages 1-3, for representation counts and the energy bounds.

In the two integer examples, the lower bounds are $256/7$ and $256/10$, and the upper bound is $64$. For the subgroup $H=\{0,2,4\}$ of $\mathbb{Z}/6\mathbb{Z}$, each element of $H$ has three sum representations, so $E(H)=3\cdot 3^2=27$ and both bounds are equalities.

For nonempty $S$, dividing additive energy by $|S{|}^3$ gives a relative measure between $1/K(S)$ and one. Small doubling constant therefore forces relatively large additive energy. A converse requires care: the Balog-Szemerédi-Gowers theorem extracts a large subset with small doubling constant, rather than asserting that all of $S$ has small doubling constant.

An algebra over a field $k$ is a vector space $A$ with a bilinear multiplication $A\times A\to A$. Bilinearity means $(ax+by)z=a(xz)+b(yz)$ and $z(ax+by)=a(zx)+b(zy)$ for $a,b\in k$. Associativity, commutativity, and a multiplicative identity are additional properties, not consequences of this definition.

The polynomial ring $k[X]$ and the matrix algebra $M_n(k)$ are associative unital examples; the latter is generally noncommutative. A Lie algebra is another kind of algebra over a field, with its bracket as multiplication, obeying antisymmetry and the Jacobi identity instead of associativity. Specifying which axioms are intended makes statements about all algebras precise.

An Archimedean ordered group with a two-sided invariant total order is commutative. If there is a least positive element, its cofinal powers exhaust the group. Otherwise each $c>1$ has $d>1$ with $d^2<c$. To see this, choose $1<s<r<c$ and use $r{s}^{-1}$ if its square is below $r$; if not, the inequality $(r{s}^{-1}{)}^2\ge r$ gives $s^2\le r<c$. If positive $g,h$ satisfied $gh<hg$, put $c=(gh{)}^{-1}hg$ and choose such a $d$. Cofinality gives $d^m\le g<d^{m+1}$ and $d^n\le h<d^{n+1}$. Two-sided order invariance then gives both $hg<d^{m+n+2}$ and $hg=ghc>d^{m+n+2}$, a contradiction. Replacing negative elements by their inverses reduces arbitrary commutativity to the positive case.

The associative property says that regrouping three inputs does not change the result of a binary operation: $(a\ast b)\ast c=a\ast (b\ast c)$ for every $a,b,c$ in its domain of a function. It changes parentheses while keeping the order of the inputs. Commutativity instead exchanges two inputs; the two properties are different.

For addition modulo three, $(2+1)+1\equiv 2+(1+1)\equiv 1(\mathrm{mod}3)$. For subtraction modulo three,so the second binary operation fails the associative property. One failed triple disproves associativity; checking a few successful triples does not establish it for all inputs.

The useful consequence is that a finite ordered sequence can be combined in chunks. For an associative operation, $(a\ast b)\ast (c\ast d)$ has the same value as $((a\ast b)\ast c)\ast d$. Intermediate results can therefore summarize parts of a computation without retaining their internal parentheses. The order must still be preserved when the binary operation is not commutative. Function composition and concatenation provide examples where grouping is harmless but exchanging entries changes the result.

For a binary operation $\oplus$, its Cartesian lifting sends lists $xs,ys$ to the list comprehension $[x\oplus y\mid x\leftarrow xs;y\leftarrow ys]$, with the right generator varying fastest. On finite lists this preserves associativity but need not preserve commutativity or idempotence, because list order and repeated entries matter.

A category specifies objects of a category, categorical morphisms between them, and composition in a category. An arrow $f:A\to B$ can be followed by $g:B\to C$, giving $g\circ f:A\to C$. Every object $A$ has an identity morphism $1_A:A\to A$, and the rules satisfyAssociativity means that grouping a chain differently does not change its composite. It does not assert commutativity, and the sources and targets must match before a composite is defined.

In the Category of sets, arrows are functions. Take two functions on the real numbers, $f(x)=x+1$ and $g(x)=2x$. Then $(g\circ f)(x)=2x+2$, whereas $(f\circ g)(x)=2x+1$. At $x=3$, the two orders give 8 and 7, respectively. Both orders are defined here because these maps share their source and target; for arbitrary arrows the reverse composite need not exist.

A partially ordered set supplies a different example: its elements are the objects of a category, with exactly one arrow $a\to b$ when $a\le b$, and none otherwise. Transitivity gives composition in a category, and reflexivity gives identity morphisms. For subsets ordered by inclusion, the two chains $\varnothing \subseteq \{a\}\subseteq \{a,b\}$ and $\varnothing \subseteq \{b\}\subseteq \{a,b\}$ have the same composite arrow. Thus arrows need not be maps of elements: they can record a relation.

For the symmetric group $S_3$, take the transpositions $x=(12)$ and $y=(23)$. Products of permutations apply the rightmost factor first. ThenThe last permutation sends $1\mapsto 3$, $3\mapsto 2$, and $2\mapsto 1$: two swaps fail to commute by an entire three-cycle.

Every group commutator has sign of a permutation $+1$, so $S_3^{\prime }\subseteq A_3$, the alternating group of even permutations. Conversely, the displayed group commutator generates $A_3=\{e,(123),(132)\}$. Therefore $S_3^{\prime }=A_3$. The two cosets are the even permutations and the odd permutations, and their multiplication is just multiplication of signs:This is the first isomorphism theorem applied to the sign of a permutation. Once commutativity is forced, all three transpositions become indistinguishable, and both three-cycles become the identity element. The surviving information is exactly whether the permutation is even or odd. Compare the very different center of a group $Z(S_3)=\{e\}$.

The finite cyclic group $C_4=\mathbb{Z}/4\mathbb{Z}$ and the Klein four-group $V_4=C_2\times C_2$ are both abelian groups of order four. In $C_4$, composition is addition modulo four. In $V_4$, label the elements $00,01,10,11$ and add each coordinate modulo two. For example, $01+10=11$ and $11+11=00$.

The order of a group element is preserved by a group isomorphism: an equation $g^m=e$ holds exactly when its image satisfies the same equation. In $C_4$, both $1$ and $3$ have order four. In $V_4$, each nonidentity element has order two. Hence these groups are not isomorphic, despite having the same order of a finite group. No relabelling can repair this discrepancy.

For a geometric model of $V_4$, take the symmetries of a non-square rectangle: the identity element, reflection in its horizontal axis, reflection in its vertical axis, and rotation through $180^{\circ }$. The two reflections commute, and their composite is the half-turn. Every nonidentity motion is its own inverse element. This makes the two binary switches concrete: choosing whether to apply each reflection specifies all four motions. The case of abelian groups of prime-square order generalizes this distinction from $p=2$ to any prime $p$.

For a positive-definite Hermitian operator $A={\sum }_j{t}_j|u_j⟩⟨u_j|$ and a unit vector $v$, the weights $|⟨v|u_j⟩{|}^2$ form a probability distribution. Scalar logarithmic concavity bounds their average of $\log t_j$ by the logarithm of their average of $t_j$. Positive semidefinite operators follow by a limiting convention. Using the eigenbasis of a density operator $\rho$ gives $S(\rho \Vert \sigma )\ge D(r\Vert q)$, where $r$ is the spectrum of $\rho$ and $q$ the diagonal of $\sigma$ in that basis. This yields nonnegativity of quantum relative entropy without commutativity.

The Dirichlet convolution of arithmetic functions $f,g$ is the arithmetic functionIn the first sum, $d$ runs over the positive integer divisors of $n$; the second uses ordered pairs of positive integers whose product is $n$. Both sums are finite. Each pair contributes one weight from $f$ and one from $g$, so Dirichlet convolution combines information attached to complementary factors. It turns a divisor sum into an operation on arithmetic functions. ^[ref]

For $n=12$ the six ordered pairs are $(1,12),(2,6),(3,4),(4,3),(6,2),(12,1)$. The constant-one arithmetic function gives one per pair, while the identity arithmetic function weights the first factor by its size:Here $\tau$ is the divisor function and ${\sigma }_1$ is the sum-of-divisors function. By comparison, the pointwise product of arithmetic functions gives $(1\cdot 1)(12)=1$ and $(\mathrm{id}\cdot 1)(12)=12$.

Commutativity follows by swapping the two entries of every ordered pair. Associativity follows by reindexing either grouping over the same ordered tuples of three positive integers:For example, $((1\ast 1)\ast 1)(12)$ counts ordered tuples of three positive integers with product $12$. Distribute the two occurrences of the prime factor $2$ among three entries in $\left(\genfrac{}{}{0ex}{}{2+2}{2}\right)=6$ ways, and the one occurrence of the prime factor $3$ in $\left(\genfrac{}{}{0ex}{}{1+2}{2}\right)=3$ ways. These binomial coefficients are the stars and bars counts of exponent choices in the nonnegative integers; prime factorization therefore gives $6\cdot 3=18$ such tuples. Directly, the same Dirichlet convolution is ${\sum }_{d\mid 12}\tau (d)=1+2+2+3+4+6=18$.

The Identity for Dirichlet convolution is $\epsilon$, and the Möbius function reverses a divisor sum because $\mu \ast 1=\epsilon$. This makes Dirichlet convolution useful both for counting factorizations and for recovering an arithmetic function from its divisor sum.

Exponentiation by squaring computes an integer power by reading the exponent's binary expansion. Appending a binary digit $b$ to a prefix of value $p$ replaces $p$ by $2p+b$, so the corresponding power changes byEach new digit requires one squaring and, only for digit one, one further multiplication. The number of digits grows with the logarithm of the exponent, making this useful for modular exponentiation, primality testing, and powers of matrices using matrix multiplication.^[ref]

For a concrete calculation, $13=(1101{)}_2=8+4+1$, so $3^{13}=3^8\cdot 3^4\cdot 3$. The optimized left-to-right algorithm used here instead keeps one accumulated power: initialize $r=3$ from the leading digit one, then process only the remaining digits $1,0,1$:Thus $3^{13}=1594323$, using three squarings and two further multiplications, instead of twelve successive multiplications starting at $3$.

For a general positive integer $n=(b_{\ell -1}\cdots b_0{)}_2$ with leading digit $b_{\ell -1}=1$, set $r=a$ and, for $i=\ell -2,\dots ,0$, first replace $r$ by $r^2$, then multiply it by $a$ if $b_i=1$. Return $r$. This explicitly skips the leading digit's otherwise unnecessary operations on one. A Computational Introduction to Number Theory and Algebra by Victor Shoup (Section 3.4, pp. 65–66) presents the version initialized at one and processing every digit; the optimization here makes the counting convention unambiguous.

The loop invariant is $r=a^p$, where $p$ is the value of the digits already read. Initially $p=1$ and $r=a$. If the next digit is $b$, then squaring and optionally multiplying give $r^{\prime }=a^{2p+b}$, exactly the next prefix. At termination $p=n$. This proof uses associativity of multiplication; it works in any monoid, including matrices with the identity matrix as identity element, and needs no commutativity between different bases.

For $n=0$, return the identity element without performing a multiplication. This is the empty-product convention $a^0=1$; if $a=0$, the algorithm therefore returns one for $0^0$ by convention, rather than resolving its meaning in every mathematical setting. Negative integer exponents require an inverse element: compute $(a^{-1}{)}^{-n}$, counting the inversion separately. Over the integers, such an inverse generally leaves the integers, and a zero base has no inverse.

A finite abelian group combines a finite set of reversible operations with commutativity. All finite cyclic groups qualify, but direct products of groups supply examples that need more than one generator of a group. The Fundamental theorem of finitely generated abelian groups says that every finite abelian group is a direct product of groups of finite cyclic groups; the finite case has no infinite cyclic factors.^[ref]

These factors distinguish different ways to have the same total number of states. A single four-position dial gives $C_4$, while two independent binary switches give $C_2\times C_2$. Both have four states and commutative composition, yet only the dial permits a single operation whose repetition visits all four states. The following Cayley tables make that distinction visible without relying on the labels alone.

Multiplication by a nonzero element $a$ of an integral domain is injective, by multiplicative cancellation. When the domain is finite, this self-map is surjective, so some element $b$ satisfies $ab=1$. Commutativity gives $ba=1$, so every nonzero element has a multiplicative inverse and the domain is a field.

Even when the domain convention does not initially assume an identity element, finiteness produces one. Surjectivity supplies $e$ with $ae=a$; then $a(ex-x)=0$ forces $ex=x$ for every $x$. Commutativity makes $e$ a two-sided identity, after which the inverse argument applies.

A unital associative algebra $A$ over a field $k$ is finitely generated when a finite set $a_1,\dots ,a_n$ generates it under addition, multiplication and scalar multiplication, including the identity element. Equivalently, every element is a finite linear combination of words in the generators. The words retain their order if multiplication is noncommutative.

In the commutative case, evaluating polynomials at the generators gives a surjective algebra homomorphismso $A$ is a quotient ring of a polynomial ring. This equivalence assumes commutativity. For a noncommutative associative algebra, the corresponding source is the free associative algebra $k⟨X_1,\dots ,X_n⟩$.^[ref]

Finite generation as an algebra differs from being finite-dimensional as a vector space. The polynomial ring $k[X]$ has one algebra generator but infinitely many linearly independent monomials $1,X,X^2,\dots$. By contrast, the quotient ring $k[X]/(X^2)$ has basis $1,\bar{X}$, and its relation truncates every higher power.

Every finite subgroup $H$ of the multiplicative group of a field is cyclic. If $m$ is the exponent of $H$, commutativity lets one combine elements whose orders realize the prime-power factors of $m$, producing an element of order $m$. Every element of $H$ is a root of $X^m-1$, so the Lagrange root bound over a field gives $|H|\le m$. Since $m\le |H|$, equality holds and that element generates $H$.

A commutative algebra over a field $k$ has a finite presentation if finitely many generators and finitely many polynomial relations describe it:The polynomial ring supplies freely chosen commuting generators, and the ideal of relations identifies expressions representing the same element. For example, $k[X,Y]/(XY-1)$ is the Laurent polynomial ring in one variable: $Y$ represents the multiplicative inverse of $X$.^[ref]

Every commutative finitely generated algebra over a field admits a finite presentation. Indeed, a field is a Noetherian ring; the Hilbert basis theorem makes its polynomial ring Noetherian, so the kernel of a chosen surjective algebra homomorphism is a finitely generated ideal. This is where commutativity enters the assertion. For a noncommutative associative algebra, a finite presentation instead uses a free associative algebra and finitely many generators for its two-sided ideal of relations; the commutative Hilbert basis theorem does not establish finite presentation there.^[ref]

A finite presentation also organizes differentiation: the module of Kähler differentials is generated by $d{X}_1,\dots ,d{X}_n$, with relations $d{f}_j={\sum }_i(\partial f_j/\partial X_i)d{X}_i$. The Jacobian matrix records those relations; this connects an algebraic description by equations to its infinitesimal geometry.

A finite sum adds finitely many terms, for example ${\sum }_{i=1}^n{a}_i=a_1+\cdots +a_n$ for a positive integer $n$. The empty sum is the additive identity. In an abelian group, the associative property and commutativity of the abelian group make the result independent of grouping and order.

The free associative algebra has a basis of finite words in its generators, including the empty word as identity. Multiplication concatenates words without commutativity relations. It is the path algebra of the quiver with r loops. With one generator it is a polynomial algebra.

The full transformation monoid consists of every self-map of $X$, with function composition as its binary operation. For $X=\{0,1\}$, there are four functions: the identity function $i$, the swap $s(0)=1,s(1)=0$, and the constant functions $c_0(x)=0,c_1(x)=1$. Their composition order matters: $c_0\circ s=c_0$, whereas $s\circ c_0=c_1$. Thus associativity does not imply commutativity.

Only $i$ and $s$ are bijections, and their inverse elements are themselves. They form a two-element group within this monoid. The constant functions instead satisfy $c_0\circ c_0=c_0$ and $c_1\circ c_1=c_1$, so they are idempotent elements of a semigroup. Such irreversible transformations explain why the monoid setting is useful even when a group would be too restrictive.