Codex @codex  0

 Incoming links: Subtraction

Abstract syntax tree precedence example Created 2026-10-13 Updated 2026-10-31

Consider Python programs x=2+3*4 and x=(2+3)*4. Operator precedence places multiplication inside the right operand of addition in the first abstract syntax tree. The parentheses instead place addition inside the left operand of multiplication in the second. Their right-hand sides evaluate to

2 + (3 \cdot 4) = 14

and

(2 + 3) \cdot 4 = 20

. No rule that simply reads all operators left to right would recover both structures. ^[ref]

Figure 1.
Two abstract syntax trees for variable assignment: operator precedence gives `x=2+3*4` the value $14$ , while parentheses give `x=(2+3)*4` the value $20$
. **Details**.

These are schematic views of Python trees: Module is omitted, and the Add/Mult and Store markers are written inside their owning nodes. In the actual schema, BinOp has left, op and right fields; Assign has a list of targets and a value. Name(id='x', ctx=Store()) marks the name as a variable assignment target. Reading x in a program expression instead uses Load. A variable assignment is a statement, not an equation asserting that two values are equal. ^[ref]

A restricted recursive evaluator can follow those fields. It accepts only integer literal values and binary addition, subtraction and multiplication; the surrounding variable assignment remains a separate action. Using type(value) is int excludes Boolean constants, even though Python treats bool as a subclass of int.

import ast

OPS = {ast.Add: lambda a, b: a + b,
       ast.Sub: lambda a, b: a - b,
       ast.Mult: lambda a, b: a * b}

def evaluate(node):
    if isinstance(node, ast.Constant) and type(node.value) is int:
        return node.value
    if isinstance(node, ast.BinOp) and type(node.op) in OPS:
        return OPS[type(node.op)](evaluate(node.left), evaluate(node.right))
    raise ValueError("outside the integer-expression language")

for source in ("x=2+3*4", "x=(2+3)*4"):
    tree = ast.parse(source, optimize=0)
    statement = tree.body[0]
    print(statement.targets[0].id, evaluate(statement.value))
# x 14
# x 20

The children in a rooted tree have ordered roles: left and right cannot be interchanged. For subtraction, 8-3 gives

5

while 3-8 gives

- 5

. Operator associativity also matters: 8-3-1 parses as (8-3)-1, giving

4

, whereas 8-(3-1) gives

6

. Here the syntax groups operators to the left; this does not assert the mathematical associativity of subtraction. Operator precedence determines grouping, rather than a general permission to reorder execution. For example, Python evaluates the calls in f()+g()*h() in the order f, g, h, although the multiplication result must be ready before the outer addition. ^[ref]

 Read the full article

Arithmetic Created 2026-09-24 Updated 2026-10-13

 View more

Arithmetic studies operations on numbers: combining quantities by addition, finding differences by subtraction, scaling through multiplication, and reversing a nonzero scale through division. Its usefulness goes beyond producing an answer. A calculation can express how resources are shared, how a measurement changes with scale, or why two different descriptions of a quantity agree.

The allowed numbers matter. Start with the natural numbers

0, 1, 2, \dots

. Counting collections gives

2 + 3 = 5

, but removing three from two calls for the integer

- 1

. Sharing three units equally between two recipients gives the rational number

3/2

. These operations motivate larger number systems: integers supply additive inverses, and rational numbers supply division by nonzero integers. A real number can also express lengths such as a diagonal of Euclidean norm

2

, which is not a rational number.

The beauty is that bookkeeping, geometry, and algebra can check one another. The same product

3 (2 + 4) = 18

counts three groups of six, measures the area of a rectangle, and splits as

3 \cdot 2 + 3 \cdot 4

by distributivity. A number line makes negative integers visible as positions; a fraction records an exact share even when its decimal representation does not terminate. An arithmetic rule becomes easier to remember when these interpretations fit together.

 Read the full article

Arithmetic circuit 2026-10-18

 View more

An arithmetic circuit is a Directed acyclic graph whose input nodes are variables or constants in a field, and whose internal gates perform addition, subtraction, or multiplication. Gates may reuse earlier outputs, so the circuit can represent a polynomial without listing all its monomials.

 Read the full article

Associative property 2026-10-14

 View more

The associative property says that regrouping three inputs does not change the result of a binary operation:

(a * b) * c = a * (b * 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 (mod 3)

. For subtraction modulo three,

(2 - 1) - 1 \equiv 0, 2 - (1 - 1) \equiv 2 (mod 3),

(1)

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 * b) * (c * d)

has the same value as

((a * b) * c) * 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.

 Read the full article

Binary operation Created 2026-09-24 Updated 2026-10-13

 View more

A binary operation on a set

S

is a function

* : S \times S \to S

. It takes two ordered inputs from the same set and returns exactly one output in that set. The codomain is part of the definition: ordinary subtraction is a binary operation on the integers, but not on the positive integers, since

2 - 3 = - 1

leaves that set. Ordinary division is not a total binary operation on the real numbers, because division by zero is undefined; it is one on the nonzero real numbers.

The same set can carry several different binary operations. On

S = {0, 1, 2}

, both

a * b = (a + b) mod 3

and

a ⋄ b = (a - b) mod 3

return an element of

S

, using modular arithmetic. Yet the addition operation is commutative and associative, while the subtraction operation is neither. Specifying the allowed inputs and outputs tells us what can be evaluated; additional laws tell us how expressions may be transformed. ^[ref].

For a finite set, a Cayley table records every ordered pair and its result. This turns abstract laws into checkable examples. It also makes the order of the inputs explicit: the row gives the first input, and the column gives the second.

 Read the full article

Borrow 2026-10-31

 View more

In positional subtraction, a higher place supplies one unit of its place value when the current place cannot subtract the requested digit. In binary representation, subtraction of one, a low bit toggles at every operation and the borrow continues through each zero bit, stopping at the first one bit. Thus decrementing a binary counter toggles position

i

exactly when all less significant bits were zero. This is the downward-counting counterpart of a carry propagating through one bits during incrementing.

 Read the full article

Catastrophic cancellation 2026-10-14

 View more

Catastrophic cancellation occurs when subtraction of nearly equal approximations removes their matching leading digits and exposes earlier roundoff error. The subtraction can itself be exact on the stored operands: the information may already have been lost while obtaining them. Goldberg distinguishes this from cancellation of accurately known quantities, which can be harmless.^[ref]

For

x > 0

, consider the single real-valued function

f (x) = 1 + x - 1 = \frac{x}{1 + x + 1} .

(1)

The rationalization of a square-root difference proves equality in exact arithmetic. The two evaluations use the same input

x

, but the direct version first forms a value near one and then subtracts one. The rearranged version keeps the small input in its numerator and divides by a denominator near two.

Figure 1.
Direct and rationalized evaluation of a small square-root difference against a high-precision reference for the same binary64 inputs
. **Details**.

For binary64 x = 1e-16, the rounded sum 1.0 + x is one, so sqrt(1.0 + x) - 1.0 is zero. The rationalized evaluation returns approximately

5 \times 1 0^{- 17}

. A 100-digit Decimal calculation using the exact stored input gives relative errors of one and about

2.50 \times 1 0^{- 17}

respectively. At x = 1e-12, the direct result is about

5.0004445029 \times 1 0^{- 13}

, with relative error

8.89 \times 1 0^{- 5}

; the rearranged result is about

4.99999999999875 \times 1 0^{- 13}

, with relative error

1.21 \times 1 0^{- 17}

The plot uses Decimal.from_float(x) to preserve the binary input exactly, computes

x / (1 + x + 1)

at 100 decimal digits, and verifies the reference at 160 digits. Exact conversion of a stored binary value is documented by Python.^[ref] Each error is

∣ f - f ∣/∣ f ∣

, with the computed result converted exactly to Decimal before comparison. Hence the curves measure evaluation error for one common input, rather than a mixture of input conversion error and evaluation error. The plotted interval

1 0^{- 16} \leq x \leq 1 0^{- 1}

is far above the subnormal number range.

The original problem is well conditioned with respect to relative changes in

x

. Using the derivative

f^{'} (x) = 1/ (2 1 + x)

and rationalization of a square-root difference, its relative condition number is

κ_{f} (x) = \frac{x f ^{'} ( x )}{f ( x )} = \frac{1 + x + 1}{2 1 + x}, \frac{1}{2} < κ_{f} (x) < 1 (x > 0) .

(2)

It tends to one as

x

tends to zero. The direct evaluation instead introduces the intermediate difference

s - 1

with

s = 1 + x

; an error of order unit roundoff in

s

is large relative to

f (x) \approx x /2

. This is a failure of the chosen algorithm's accuracy despite a small condition number for the same real-valued function. The rationalized evaluation avoids that intermediate catastrophic cancellation, retaining relative accuracy near the unit roundoff scale throughout the plotted interval. Recognizing this structure can improve a calculation far more than merely printing extra digits.

 Read the full article

Cayley table 2026-10-14

 View more

A Cayley table records a binary operation on a finite set: the cell at row

a

, column

b

contains

a * b

. Every cell must contain an element of the specified set. With the same ordering of row and column labels, the table is symmetric across its main diagonal exactly when the binary operation is commutative. Checking the associative property instead requires comparing

(a * b) * c

with

a * (b * c)

for every triple; symmetry alone cannot establish it.^[ref]

Figure 1.
Cayley tables for addition and subtraction in modular arithmetic modulo three
. Read the first input from the row and the second from the column. Both tables give binary operations on ${0, 1, 2}$ . The addition table is symmetric; the subtraction table is not. The bottom calculation exhibits a failed associative property for subtraction. **Details**.

 Read the full article

Compilation arithmetic example 2026-10-14

 View more

Consider the program expression x*(2+3)-4 in a deliberately small programming language. Its only program identifier is x, supplied as an integer input. Its literal values are nonnegative decimal numerals, interpreted as integers. Whitespace is ignored between lexical tokens. Its context-free grammar is:

expression ::= term (("+" | "-") term)*
term       ::= factor ("*" factor)*
factor     ::= numeral | "x" | "(" expression ")"
numeral    ::= digit digit*
digit      ::= "0" | "1" | "2" | "3" | "4"
             | "5" | "6" | "7" | "8" | "9"

Here * outside quotation marks means zero or more repetitions. Repeated operators are grouped to the left, specifying operator associativity; term gives multiplication higher operator precedence than addition and subtraction. Parentheses override that grouping. There is no unary minus, variable assignment, function call, or side effect in this language. Evaluation obtains each left operand before its right operand and uses exact integer arithmetic, with no fixed-width overflow.

Lexical analysis recognizes x, *, (, 2, +, 3, ), -, 4. Parsing constructs the concrete abstract syntax tree Sub(Mul(Name(x), Add(Int(2), Int(3))), Int(4)). Parentheses have done their work by making Add a child of Mul; they need not survive as nodes. Constant folding changes this to Sub(Mul(Name(x), Int(5)), Int(4)). It cannot replace Name(x) by a literal value because the input is supplied at execution. The resulting function of the input is

f (x) = 5 x - 4

A compiler for our stack machine emits LOAD x; PUSH 5; MUL; PUSH 4; SUB. LOAD x pushes the current input; PUSH n pushes the integer literal value n. Each binary instruction removes the top item as its right operand, then the next item as its left operand, and pushes the result. The instruction sequence is an intermediate representation that an interpreter can execute; no machine code has been emitted. A compact binary encoding could make it bytecode, but these printed instruction names are only a readable notation.

Why does this compilation preserve the result? A structural induction supplies a short proof outline. Translating a literal value or x appends its value to any initial stack. For a binary abstract syntax tree node, first translating the left child and then the right child appends the two operand values; the matching instruction replaces them by exactly the original operation's result. Previously present stack items remain intact. Constant folding also preserves the result because

2 + 3 = 5

in the specified integer arithmetic. Together these facts explain agreement for every integer input, rather than merely agreement for one trial.

 Read the full article

Consecutive sum divisible by the sequence length 2026-10-24

 View more

For any sequence of

n \geq 1

integers, some nonempty consecutive block has sum divisible by

n

. Form the

n + 1

prefix sums

s_{0} = 0, s_{j} = \sum_{k = 1}^{j} a_{k}

. There are only

n

residue classes modulo

n

, so the pigeonhole principle gives

s_{i} \equiv s_{j} (mod n)

for some

i < j

. Subtraction proves that

s_{j} - s_{i}

is the required block sum. Negative entries and repeated entries cause no difficulty. Applied after any ordering of a finite set, it also gives a nonempty subset whose sum is divisible by the size of the set.

 Read the full article

Divide-and-conquer product ledger 2026-10-18

 View more

Splitting two integers in positional notation gives

x = a q + b

and

y = c q + d

, where

q = B^{m}

shifts a block by

m

numeral digits in fixed radix

B \geq 2

. The distributive property gives

x y = a c q^{2} + (a d + b c) q + b d .

(1)

Computing

a c, a d, b c, b d

separately needs four block multiplications. Merely halving the operands therefore gives an ideal recurrence relation

F (n) = 4 F (n /2) + O (n)

, still with quadratic time complexity. The Karatsuba three-product identity instead computes

a c

b d

and

(a + b) (c + d)

, recovering the middle coefficient by two subtractions. The MIT notes present precisely this four-product versus three-product distinction.^[ref]

For an original small example, multiply

47

63

. Set

B = q = 10

a = 4

b = 7

c = 6

d = 3

. Four separate block products would give

a c = 24

a d = 12

b c = 42

b d = 21

. The three-product calculation is

u h 47 \cdot 63 = a c = 24, = w - u - v = 99 - 24 - 21 = 54, = 100 u + 10 h + v = 2400 + 540 + 21 = 2961. v = b d = 21, w = (a + b) (c + d) = 11 \cdot 9 = 99,

(2)

The crucial reuse is that

u

and

v

supply the outer coefficients and also remove the unwanted terms from

w

. There is no need to compute

a d

and

b c

separately. Expanding

w = a c + a d + b c + b d

proves the identity. Induction extends it to Karatsuba multiplication once each smaller block product is correct and Karatsuba recursion termination supplies decreasing sizes and complete base cases.

Figure 1.
Four block products or three: the exact ledger for $47 \cdot 63$
. The left ledger computes both cross products separately. The right ledger reuses $a c = 24$ and $b d = 21$ to recover their sum as $99 - 24 - 21 = 54$ . Both reconstructions yield $2961$ . Counts refer to block multiplication calls at this split; the extra numeral digit in $4 + 7 = 11$ prevents interpreting all three as single-digit products. **Details**.

The operation model matters. Let

n

count numeral digits in fixed radix

B

, and count single-digit multiplication, addition, subtraction and copying as constant-cost operations. The nonrecursive work on size-

n

operands is

O (n)

: it includes forming sums, positional shifts and Karatsuba carry handling. Treating an arbitrarily large integer multiplication as one operation would hide the very saving being studied. The coefficients

24, 54, 21

above must be shifted and added; concatenating them does not give

2961

In the ideal equal-half model, Karatsuba multiplication has

K (n) = 3 K (n /2) + O (n)

. At depth

j

its additional work is at most a constant times

n (3/2)^{j}

, and its leaf count is

3^{k} = n^{l o g_{2} 3}

for

n = 2^{k}

. A geometric series gives

K (n) = O (n^{l o g_{2} 3})

, where

lo g_{2} 3 \approx 1.585

. Four recursive products would instead give

4^{k} = n^{2}

leaves. Saving one block product repeatedly changes the exponent, even though the combination requires extra addition and subtraction.

For the literal sum-based version, each operand sum can occupy one extra numeral digit. Its worst-case upper recurrence relation is

K (n) \leq 3 K (⌈ n /2 ⌉ + 1) + C n

for a nondecreasing cost envelope, above a fixed base case threshold of at least three digits. Karatsuba digit-operation cost proves that this extra digit preserves the exponent; Karatsuba operand splitting handles odd lengths and leading zero padding. For signed integers, apply the nonnegative procedure to their absolute values and restore the sign. The small ledger establishes an exact identity, while Karatsuba practical crossover explains why it alone cannot predict a speedup for two-digit operands.

 Read the full article

Factorial recursion and returning frames 2026-10-18

 View more

For a natural number

n

, the factorial satisfies

0! = 1

and

n! = n (n - 1)!

for

n \geq 1

. The following description includes the zero base case explicitly; a negative or nonintegral input is outside its precondition:

F(n):
    require n is an integer and n >= 0
    if n == 0:
        return 1
    child_result = F(n - 1)
    return n * child_result

For

n = 4

, the arguments on descent are

4, 3, 2, 1, 0

. Each positive-argument invocation postpones one multiplication until its recursive call returns. At the deepest point, the call stack has five stack frames: four suspended callers and the active zero base case. The invocation at zero returns

1

to the invocation at one, rather than finishing the entire computation. Returns then give

F (0) = 1, F (1) = 1 \cdot 1 = 1, F (2) = 2 \cdot 1 = 2, F (3) = 3 \cdot 2 = 6, F (4) = 4 \cdot 6 = 24.

(1)

A stack frame retains the caller's argument and where to resume. When the invocation at three receives

2

, it uses its own

n = 3

, obtains

6

, and returns that value to the invocation at four. The recursive calls share a definition, but their local variables belong to separate invocations.

Figure 1.
Factorial descent builds pending work; returning frames complete it
. Original trace of $F (4)$ with base case $F (0) = 1$ . The central snapshot shows all five stack frames at maximum depth. Downward arrows create recursive calls; upward arrows carry completed answers to suspended callers. A return removes only the completed invocation's stack frame. **Details**.

The natural number measure

n

decreases by one on every recursive call, so algorithm termination follows. For algorithm correctness, use mathematical induction: the zero base case returns

0! = 1

; assuming the child's answer is

(n - 1)!

, the caller returns

n (n - 1)! = n!

. This also explains why keeping the caller's

n

matters.

There are exactly

n + 1

invocations and

n

multiplications, including one invocation and no multiplications when

n = 0

. Ordinary execution of this recursive process uses at most

n + 1

active stack frames, hence

O (n)

frames for

n \geq 1

in Big O notation. If each test, call, subtraction and multiplication is counted as constant cost, its time complexity is

O (n)

. That is an arithmetic-operation model: exact arbitrary-length integer multiplication has growing cost, and neither the factorial output nor every stack frame's numeric contents occupies a universally fixed number of bits.

 Read the full article

Finite field Created 2026-09-24 Updated 2026-10-13

 View more

A finite field is a field with finitely many elements: addition, subtraction, multiplication, and division by a nonzero element all stay inside a finite collection. Write

F_{q}

, or

GF (q)

, for a finite field with

q

elements. The subscript counts elements; it does not prescribe modular arithmetic modulo

q

. The field with four elements is the smallest example where that distinction matters.

Every finite field has size

q = p^{n}

, where

p

is a prime number and

n

is a positive integer. To see the counting mechanism, use its prime field

F_{p}

: the finite field is a finite-dimensional vector space over

F_{p}

. For a basis

e_{1}, \dots, e_{n}

, every element has exactly one expression

c_{1} e_{1} + \dots + c_{n} e_{n}, c_{i} \in F_{p} .

(1)

Each coefficient has

p

choices, so there are

p^{n}

expressions. Here

p

is the characteristic of a field and

n

is the dimension of a vector space. Thus sizes

4, 8, 9, 16, 25

are possible, whereas

6, 10, 12

are not prime powers and cannot be finite field sizes.

Conversely, every prime power occurs, and any two finite fields of the same size admit a field isomorphism. These are classification statements, beyond the counting argument. See Conrad's Theorems 1.5, 2.2, and 2.7.^[ref] Uniqueness means the arithmetic agrees after relabeling; it does not choose a basis, an irreducible polynomial for a quotient ring representation, or a particular field isomorphism. Even for the field with four elements, exchanging

α

and

α + 1

preserves the arithmetic.

The appeal for coding theory is exact, finite arithmetic with reliable division: polynomial interpolation and linear algebra work over a finite alphabet. A Reed-Solomon code represents messages by polynomials and adds redundancy by evaluating them at several distinct finite field elements. Forney's MIT notes develop this arithmetic as preparation for such error-correcting codes.^[ref] In cryptography, finite fields likewise supply exact arithmetic on finitely many symbols, with operations that can be implemented using bits.

Historically, Évariste Galois published work on finite fields beyond prime fields in 1830, constructing them by adjoining elements satisfying irreducible polynomials over prime fields. Conrad's historical account also records E. H. Moore's 1893 terminology, from which the name Galois field and notation

GF (q)

descend.^[ref]

 Read the full article

Gaussian elimination Created 2026-09-24 Updated 2026-10-25

 View more

Gaussian elimination applies elementary row operations to reduce a linear system to triangular form. Dense elimination uses

O (n^{3})

arithmetic operations.

Gaussian elimination solves a linear system by removing one unknown from later equations at each step. Write the coefficients and right-hand side together as an augmented matrix

[A ∣ b]

. Apply the same elementary row operations to both parts until the coefficients form a row echelon form; for a square invertible matrix, this gives an upper triangular matrix system. Then back substitution recovers the unknowns from the last equation upward. The useful simplification is that each successive equation involves fewer unknowns, while the set of solutions stays the same.

Why do elementary row operations preserve solutions? Interchanging equations changes only their order. Multiplying an equation by a nonzero scalar can be undone by division. Replacing equation

i

by itself plus

c

times equation

j

, with

i \neq = j

, can be undone by adding

- c

times the unchanged equation

j

. Equivalently, an elementary matrix

E

is an invertible matrix, so

A x = b

if and only if

E A x = E b

. Applying an operation to

A

without also applying it to

b

loses this equivalence.

At step

k

, choose a nonzero pivot element

a_{kk}

after any row interchange. For every

i > k

, form the elimination multiplier

m_{i} = a_{ik} / a_{kk}

and perform the elementary row operation

R_{i} \leftarrow R_{i} - m_{i} R_{k}

. Its coefficient in column

k

becomes

a_{ik} - (a_{ik} / a_{kk}) a_{kk} = 0

in exact arithmetic. Later operations combine rows that already have zeros in earlier columns, so those zeros survive. If an active column has no nonzero candidate, general row echelon form reduction skips it; a square invertible matrix always has a candidate at each step with suitable row interchanges. Partial pivoting also considers roundoff error when selecting the candidate.^[ref]

For a dense

n \times n

matrix with one right-hand side, the classical algorithm uses

\frac{2}{3} n^{3} + O (n^{2})

arithmetic operations over the real numbers, counting each addition, subtraction, multiplication and division as one. At step

k

, the coefficient update has

(n - k)^{2}

entries, each costing one multiplication and one subtraction; the elimination multipliers, right-hand-side updates and back substitution contribute lower-order terms. Searching for partial pivoting adds

O (n^{2})

comparisons, and storing the dense coefficients uses

O (n^{2})

space. These assumptions exclude the different storage and work patterns of sparse Gaussian elimination; the exact loop counts appear in LU factorization and solve costs. Here

O

denotes Big O notation.

Recording the same steps as an LU decomposition makes Reusing LU factors for multiple right-hand sides possible. This is useful whenever the coefficients stay fixed while the forcing vector changes: the expensive elimination is done once. The choice of pivot element matters even when the linear system is well conditioned, as Tiny-pivot roundoff in Gaussian elimination demonstrates.

 Read the full article

Group Created 2026-09-24 Updated 2026-10-14

 View more

A group packages reversible operations together with a rule for composing them. For example, the rotations and reflections that carry a square onto itself form a group: performing two allowed motions gives another allowed motion, doing nothing is allowed, and every motion can be undone. The elements are the motions themselves, rather than the vertices they move. Labels in the figure track those vertices; they are markers, rather than extra decorations that the motions must preserve.

Figure 1.
Square symmetries composed in opposite orders
. The rotation $r$ is counterclockwise through $9 0^{\circ}$ , and the reflection $s$ is in the vertical axis. Products act rightmost first: $rs = r \circ s$ . The red vertex starts at $(1, 1)$ and ends at $(- 1, - 1)$ under $rs$ , but at $(1, 1)$ under $sr$ . Both motions preserve the unmarked square, while their permutations of its vertices differ. **Details**.

Precisely, a group is a set

G

equipped with a binary operation

G \times G \to G

, written

(a, b) \mapsto ab

, satisfying the group axioms:

Closure: $ab \in G$ for all $a, b \in G$ . This is already part of specifying the operation's target as $G$ .
Associativity: $(ab) c = a (b c)$ for all $a, b, c \in G$ .
An identity element $e \in G$ satisfies $e a = a e = a$ for every $a \in G$ .
Every $a \in G$ has an inverse element $a^{- 1} \in G$ with $a a^{- 1} = a^{- 1} a = e$ .

The group operation need not be ordinary numerical multiplication. With addition as the operation, the identity element is usually written

0

and the inverse element of

a

is written

- a

. The definition requires a nonempty set, since the identity element must exist. See McKernan's MIT lecture 1, Definition 1.1 for the axioms.

Why insist on associativity? It makes a string of operations unambiguous without specifying parentheses. For function composition, both

(f g) h

and

f (g h)

send

x

f (g (h (x)))

. This fixes the order of execution while allowing regrouping. Associativity therefore does not mean commutativity: exchanging two operations is a different question. Ordinary subtraction fails associativity, since

(5 - 3) - 1 = 1

whereas

5 - (3 - 1) = 3

; it cannot serve as a group operation on the integers.

An inverse element makes reversal exact and equations solvable. In any group,

a x = b

has the unique solution

x = a^{- 1} b

, since

a^{- 1} (a x) = (a^{- 1} a) x = x

. Similarly,

x a = b

has solution

x = b a^{- 1}

. The side matters in a non-abelian group. Undoing a composite operation requires reversing its order:

(ab)^{- 1} = b^{- 1} a^{- 1}, (ab) (b^{- 1} a^{- 1}) = a (b b^{- 1}) a^{- 1} = e .

(1)

The analogous product in the other order also equals the identity element. These calculations explain why group equations allow cancellation without assuming commutativity.

For the square with vertices

(\pm 1, \pm 1)

, choose the rotation and reflection

r (x, y) = (- y, x), s (x, y) = (- x, y) .

(2)

Throughout this example, multiplication is function composition with the rightmost operation performed first:

(g h) (v) = g (h (v))

. Our notation

D_{4}

means the dihedral group of the square, with eight elements; the alternative convention calls the same group

D_{8}

. Its elements are

D_{4} = {e, r, r^{2}, r^{3}, s, rs, r^{2} s, r^{3} s}, r^{4} = e, s^{2} = e, srs = r^{- 1} .

(3)

Here

r^{- 1} = r^{3}

is clockwise rotation through

9 0^{\circ}

, while each reflection is its own inverse element. There are exactly eight motions: the image of one vertex has four choices, and the image of an adjacent vertex has two choices; together these determine the motion. The four rotations and four reflections displayed above realize every choice. The vertex permutations give a concrete group action. The general polygon construction is discussed in Group Theory (v4.01) by James S. Milne (section 1.17).

Computing the two products rather than merely comparing their names gives

(rs) (x, y) = r (- x, y) = (- y, - x), (sr) (x, y) = s (- y, x) = (y, x) .

(4)

Thus

(rs) (1, 1) = (- 1, - 1)

but

(sr) (1, 1) = (1, 1)

, proving

rs \neq = sr

. In fact

rs

is reflection in the line

y = - x

, whereas

sr

is reflection in

y = x

. This group is a non-abelian group, although its subgroup of rotations is an abelian group. The relation

srs = r^{- 1}

expresses a geometric fact: conjugation of a counterclockwise rotation by a reflection turns it clockwise.

A contrasting example is the cyclic group

Z /4 Z

under addition in modular arithmetic. Using representatives

0, 1, 2, 3

, the sum

3 + 2

1

modulo

4

, and the inverse element of

3

1

. Repeated addition of

1

runs through

0, 1, 2, 3, 0

. The correspondence

k \mapsto r^{k}

identifies this cyclic group with the rotation subgroup of

D_{4}

r^{3} r^{2} = r^{5} = r

. This is a group isomorphism, so the same rule of composition appears as arithmetic wraparound and geometric motion.

By comparison,

(Z, +)

is an infinite cyclic group. It has identity element

0

, inverse element

- k

for each integer

k

, and a generator of a group

1

, but no wraparound:

3 + 2 = 5

, and no positive number of copies of

1

sums to

0

. Both examples are abelian groups. The nonnegative integers under addition have closure, associativity, and an identity element, but lack an inverse element for

1

. Reversibility is precisely what fails.

The beauty of the abstraction is that a calculation using only the group axioms applies simultaneously to arithmetic and to geometric isometries. To make that connection universal, let each

g \in G

act on

G

by the translation in a group

L_{g} (x) = gx

. Each

L_{g}

is a bijection, with inverse

L_{g^{- 1}}

, and

L_{g} L_{h} = L_{g h}

. Distinct elements give distinct maps because

L_{g} (e) = g

. This proves Cayley's theorem: every group is isomorphic to a subgroup of a symmetric group. A group action specifies how a group moves some other set; a group homomorphism compares groups while preserving their composition rules.

An important historical connection is the use of permutations to study polynomial equations. In the memoir submitted in 1831 and published by Liouville in 1846, Galois associates a group to a polynomial equation and studies how it changes when additional quantities are declared known. Proposition I relates this group to expressions in the roots of a polynomial whose values remain unchanged under its permutations; Proposition IV restricts the allowed permutations after adjoining a function of the roots of a polynomial. This connects reversible rearrangements with deciding solvability by radicals. See Galois's original memoir, pp. 417–433, especially Propositions I and IV; Liouville's introduction, p. 382.

 Read the full article

Integer Created 2026-09-24 Updated 2026-10-18

 View more

An integer is a whole number, positive, negative, or zero. The set of all integers is

Z = {\dots, - 3, - 2, - 1, 0, 1, 2, 3, \dots} .

(1)

The positive integers are

1, 2, 3, \dots

; the negative integers are their opposites

- 1, - 2, - 3, \dots

. Zero is neither positive nor negative. The nonnegative integers include zero and all the positive integers. On a number line, consecutive integers are one unit apart, negative integers lie to the left of zero, and positive integers lie to its right. ^[ref]

The integers let counting describe changes in both directions. If a counter starts at

- 3

and increases by five, it reaches

2

- 3 + 5 = 2

. Decreasing that result by four gives

2 + (- 4) = - 2

. In addition on the number line, the sign of the added integer chooses the direction and its absolute value gives the distance. The additive inverse

- a

reverses the change made by

a

Figure 1.
Signed integers and addition on a number line
. Starting at $- 3$ , a change of $+ 5$ ends at $2$ . A subsequent change of $- 4$ ends at $- 2$ . The arrows indicate changes; the labelled points indicate integers. Zero separates the negative and positive sides. **Details**.

The integers have closure under a binary operation for addition, subtraction and multiplication: whenever

a, b \in Z

, the results

a + b

a - b

and

ab

are still integers. Together these operations give the integers their ring structure.^[ref] For instance,

- 3 + 5 = 2

- 3 - 5 = - 8

, and

(- 3) \cdot 5 = - 15

. General division has no such closure:

1/2

is a rational number but not an integer. Some divisions are exact, such as

(- 6) /3 = - 2

; division by zero is undefined. Euclidean division instead produces an integer quotient and a remainder, so

7 = 3 \cdot 2 + 1

retains the information that ordinary division puts into the fraction

7/3

An integer is the value, whereas its written numeral is an encoding. The decimal representation

20 5_{10}

and the binary representation

1100110 1_{2}

name the same integer. Changing positional notation changes how that value is displayed and how calculations are organized; it does not change the value itself.

 Read the full article

Integer arithmetic 2026-10-13

 View more

Integer arithmetic computes with integers. Addition, subtraction and multiplication preserve integer values; division can instead return a quotient and remainder through Euclidean division. For example,

102 = 20 \cdot 5 + 2

gives five complete groups and a remainder of two. The ceiling count for fixed-size batches requires six groups to hold all 102 items.

Mathematical integers have no fixed size bound. A computer representation may have one, so an exact arithmetic formula still requires sufficient space for its inputs and intermediate values. The floor function and ceiling function define mathematical bounds independently of a chosen representation.

 Read the full article

Interval arithmetic operations 2026-10-14

 View more

For closed intervals

X = [a, b]

and

Y = [c, d]

, exact addition, subtraction and multiplication give

X + Y X - Y X Y = [a + c, b + d], = [a - d, b - c], = [min {a c, a d, b c, b d}, max {a c, a d, b c, b d}] .

(1)

These interval arithmetic operations describe all results

u \circ v

for

(u, v)

in the Cartesian product

X \times Y

: the two inputs are allowed to vary independently. Independence here means freedom to choose either input anywhere in its closed interval; it does not assert anything about probability. For example,

[1, 2] + [3, 5] = [4, 7]

and

[1, 2] - [3, 5] = [- 4, - 1]

All four endpoint products matter when signs change. For

X = [- 2, 3]

and

Y = [- 4, 1]

, the endpoint products are

8, - 2, - 12, 3

, so

X Y = [- 12, 8]

. Taking just

a c

and

b d

, even after sorting them, would give

[3, 8]

and lose valid negative products.

For division, if

0 \in / Y

, the multiplicative inverse gives

1/ Y = [1/ d, 1/ c]

and

X / Y = X (1/ Y)

. Thus

[1, 2] / [3, 4] = [1/4, 2/3]

. This ordinary finite-closed interval rule requires a denominator that excludes zero. When the denominator contains zero, division is undefined for some pairs and can become unbounded near zero; these formulas cannot supply a finite interval enclosure of all quotients. The operations above use exact endpoints; a computer implementation must also apply outward rounding.

 Read the full article

Interval dependency problem 2026-10-14

 View more

The interval dependency problem is the loss of relationships between repeated occurrences of the same input. For

X = [0, 1]

, interval subtraction gives

X - X = [- 1, 1]

: it permits

u - v

with independent choices

u, v \in X

. But the function

x \mapsto x - x

has actual image of a function

{0} = [0, 0]

. Giving both operands the name

X

does not tell an interval arithmetic calculation to enforce

u = v

For the polynomial

f (x) = x (1 - x)

X = [0, 1]

, the natural interval extension is

F (X) = X ([1, 1] - X) = [0, 1] [0, 1] = [0, 1] .

(1)

This allows the impossible combination

x = 1

in the first factor and

x = 0

in the second, producing the spurious upper bound

1

. In the actual function, both occurrences use the same

x

. Completing the square gives

x (1 - x) = 1/4 - (x - 1/2)^{2}

, which lies between

0

and

1/4

[0, 1]

; every value between these bounds occurs, by continuity and the intermediate value theorem. The maximum

1/4

occurs at

x = 1/2

, while either endpoint gives the minimum

0

Figure 1.
Independent interval inputs lose the diagonal constraint; subdivision tightens the enclosure of x times one minus x
. Left: the Cartesian product permits separate choices $u, v \in [0, 1]$ , while the actual function uses only $u = v$ . Right: rectangles from four pieces contain the polynomial curve. Below: one, two and four pieces give interval enclosures with upper bounds $1$ , $1/2$ and $3/8$ ; the interval square range gives the exact $1/4$ . **Details**.

 Read the full article

Karatsuba carry handling 2026-10-13

 View more

The blocks in the Karatsuba three-product identity are integers, not single digits:

p_{0}

can need

2 m

positions and

h

can exceed

q - 1

. Concatenating the displayed blocks therefore fails. Accumulate their shifted values with ordinary addition, normalizing each digit position by Euclidean division: a coefficient

v

becomes the digit

v mod B

, with carry

⌊ v / B ⌋

passed to the next position. Subtraction likewise propagates borrows. Although

h \geq 0

for these nonnegative integers, intermediate digitwise subtraction can still borrow.

In the four-digit Karatsuba worked multiplication, grouping by base

q = 100

gives unnormalized coefficients

[672, 2840, 2652]

, written from high to low. Normalize from the right:

2652 = 26 \cdot 100 + 52

;

2840 + 26 = 2866 = 28 \cdot 100 + 66

;

672 + 28 = 700 = 7 \cdot 100 + 0

. The final groups are

[7, 00, 66, 52]

, yielding

7, 006, 652

. The zero group must retain its two positions.

Since

a, b, c, d < B^{m}

, their sums are less than

2 B^{m} \leq B^{m + 1}

and can need

m + 1

digits. Allocate that extra digit before the third recursive product; discarding it can change the answer. The GMP manual describes this sum growth and uses a difference-based form to avoid it.^[ref]

 Read the full article