Let be an integrally closed domain and monic, with discriminant outside a prime ideal . The roots stay distinct after reduction. In the splitting algebra choose a prime above . Its decomposition group maps onto the Galois group of the residue splitting field; its inertia group fixes every reduced root and is trivial because reduction bijects the distinct root sets. Thus the residue Galois group embeds in the generic group as a permutation group. For finite residue fields, irreducible factor degrees give the Frobenius cycle type.
Unsigned Stirling number of the first kind Created 2026-10-20 Updated 2026-11-05
The unsigned Stirling number of the first kind is the number of permutations on labels with disjoint permutation cycles. It satisfies
with impossible indices giving zero. Either label forms its own cycle, or it is inserted immediately after one of the old labels in an existing cycle; deleting reverses either construction. Thus . The same recurrence relation gives the coefficient identity .
A verifier in an interactive proof is the efficient participant that evaluates a public statement using messages from a prover in an interactive proof and its own random choices. Its algorithm specifies which challenge to send, how to process the response and when to accept or reject. In the standard model it runs in probabilistic polynomial time in the public input length.[ref]
The verifier's guarantee concerns more than one successful conversation. Completeness of an interactive proof requires a suitable honest prover to succeed on true statements. Soundness of an interactive proof bounds success of every cheating strategy on false statements. A verifier that accepts whenever it receives any message meets neither requirement merely by being fast.
For an original checking example, suppose a response claims a graph isomorphism between two20-vertex graphs encoded by adjacency matrices. Checking that the vertex mapping is a bijection and that all adjacency entries agree with their mapped entries verifies that response. It does not require searching through all vertex permutations.
An interactive proof system can use such inexpensive checks in a randomized conversation. The verifier's random choices must follow the specified protocol: exposing a challenge too early, reusing randomness in an unjustified way or changing the acceptance rule can alter its mathematical guarantees.
Vieta's formulas Created 2026-10-18 Updated 2026-10-20
Vieta's formulas connect two descriptions of a polynomial: its coefficients and its roots of a polynomial. They let us read the sum and product of the roots of a polynomial without finding the individual roots of a polynomial, and turn a proposed factorization of polynomials into checkable coefficient identities. The key is that coefficients encode elementary symmetric polynomials, which are unchanged by a permutation of the roots of a polynomial.
For a polynomial of polynomial degree , with nonzero leading coefficient , write its factorization of polynomials in a splitting field as
List every root of a polynomial according to its multiplicity of a root. Then
In particular, and . With coefficients in the real numbers or complex numbers, the fundamental theorem of algebra ensures that a list of roots of a polynomial in the complex numbers exists when multiplicity of a root is counted.[ref]
For a monic polynomial, this is the familiar convention
where is the th elementary symmetric polynomial in the roots of a polynomial; in particular, . The ratio by in the general statement matters: multiplying every coefficient by the same nonzero scalar preserves both the roots of a polynomial and these ratios.
A short derivation explains every alternating sign. In the product , a term of polynomial degree arises by choosing from distinct factor positions and from the others. Summing the resulting products gives . Values at different positions may coincide: the selection is of positions, not distinct root values. Matching coefficients gives the formula. This is the distributive property organized by the number of chosen root factors.
Weakly symmetric channel capacity Created 2026-09-24 Updated 2026-10-25
For a discrete memoryless channel with output symbols, suppose every row of the transition matrix is a permutation of every other row and all column sums agree. Such a communication channel has
The row Shannon entropy is the same for every input, so has that fixed value for every input probability distribution. The remaining term is at most by maximum entropy on a finite alphabet.
A uniform input attains the bound. If there are input symbols, the total of all transition probabilities in the matrix is ; equal column sums must therefore each be . Multiplication by the uniform input mass gives output mass in each column. Hence , which proves the displayed formula. The cyclic ternary channel capacity, binary symmetric channel capacity, and ternary symmetric channel capacity are concrete applications of this symmetry calculation.
Weighted Hamilton cycle 2026-10-14
A weighted Hamilton cycle is a Hamilton cycle in a weighted graph, with cost equal to the sum of its traversed edge weights. Here weights represent symmetric nonnegative costs, rather than conductances. Asking whether a Hamilton cycle exists is a feasibility question; asking for the cheapest one is an instance of the travelling salesman problem. A complete graph supplies every possible connection between distinct vertices, making feasibility automatic for , while choosing the cheapest visiting order remains a separate mathematical optimization problem.
Figure 1.
A fictitious weighted graph on four vertices: its three Hamilton cycles, identified under reversal and cyclic rotation, have costs 14, 19 and 21
. Details.
Assign the complete graph the symmetric edge costs , , , , and , in arbitrary units. Fix the start at and identify each Hamilton cycle with its reverse. The three possibilities are
These exhaust the possibilities: the permutations of the other three vertices give orders, paired into three reversals. Hence the perimeter tour really is optimal for this toy instance. The diagram's geometric lengths are not costs, and no triangle inequality is assumed.
The usefulness of this model is to distinguish visiting required sites from covering required connections. If tasks are assigned to vertices and the route must return after one visit to each, a weighted Hamilton cycle captures the ordering requirement. If the job instead requires each edge once, the relevant object is an Euler circuit. The shortest path problem asks only for a cheapest route between specified endpoints. A 1954 primary research paper gave a concrete motivation for the travelling salesman problem: certify that a particular tour through 49 cities has minimum road-distance cost.[ref]
These are abstract route models. If a cost stands for a whole graph path through an underlying network, travelling between consecutive task vertices can pass through intermediate network vertices more than once. One visit per task therefore does not imply one visit per physical junction. One-way connections require a directed graph; changing costs or extra timing constraints require a richer model than the fixed symmetric toy instance.
For a permutation of an orthonormal basis, the weighted image columns are mutually orthogonal and have squared norms . Hence and the displayed criterion follows. All nonzero weights suffice for invertibility, but unitarity requires unit-modulus weights. This describes basis permutations decorated by phases without introducing unwanted changes of amplitude.
Zero-knowledge simulator 2026-11-05
A zero-knowledge simulator is an efficient randomized algorithm that reproduces the relevant verifier-view distribution of a zero-knowledge proof without receiving the prover's secret cryptographic witness. Depending on the definition, the real and simulated views must be identical, statistically close or satisfy computational indistinguishability.[ref]
The graph-isomorphism proof protocol provides an illuminating example for honest-verifier zero knowledge. On a fixed public isomorphic pair , a real prover sends a random relabeling , receives a uniform challenge bit , and supplies a graph isomorphism from to .[ref]
An explicit simulation reverses that construction. First choose a uniform bit and a uniform vertex permutation . Set
and output the transcript . The simulator never needs a mapping between and . For an isomorphic public pair, random relabelings of either graph have the same probability distribution; conditional on , the response mapping is uniform in both constructions. Thus the honest verifier's transcript distribution is reproduced exactly.
This does not give a live cheating prover control of the verifier's future challenge. The simulator chooses a complete transcript in a different order from the real exchange. Nor does this simple sampler establish security against an arbitrary malicious verifier, whose challenge could depend on .
The example exposes the central requirement: producing one plausible accepting transcript is insufficient. The simulator must reproduce the specified distribution within the required efficiency bound and adversary model.