Zlil Sela

Zlil Sela is an Israeli mathematician working in the area of geometric group theory.
He is a Professor of Mathematics at the Hebrew University of Jerusalem. Sela is known for the solution of the isomorphism problem for torsion-free word-hyperbolic groups and for the solution of the Tarski conjecture about equivalence of first-order theories of finitely generated non-abelian free groups.
Biographical data.
Sela received his Ph.D. in 1991 from the Hebrew University of Jerusalem, where his doctoral advisor was Eliyahu Rips.
Prior to his current appointment at the Hebrew University, he held an Associate Professor position at Columbia University in New York. While at Columbia, Sela won the Sloan Fellowship from the Sloan Foundation.
Sela gave an Invited Address at the 2002 International Congress of Mathematicians in Beijing. He gave a plenary talk at the 2002 annual meeting of the Association for Symbolic Logic,
and he delivered an AMS Invited Address at the October 2003 meeting of the American Mathematical Society and the 2005 Tarski Lectures at the University of California at Berkeley.
He was also awarded the 2003 Erdős Prize from the Israel Mathematical Union.
Sela also received the 2008 Carol Karp Prize from the Association for Symbolic Logic for his work on the Tarski conjecture and on discovering and developing new connections between model theory and geometric group theory.
Mathematical contributions.
Sela's early important work was his solution in mid-1990s of the isomorphism problem for torsion-free word-hyperbolic groups. The machinery of group actions on real trees, developed by Eliyahu Rips, played a key role in Sela's approach. The solution of the isomorphism problem also relied on the notion of "canonical representatives" for elements of hyperbolic groups, introduced by Rips and Sela in a joint 1995 paper. The machinery of the canonical representatives allowed Rips and Sela to prove algorithmic solvability of finite systems of equations in torsion-free hyperbolic groups, by reducing the problem to solving equations in free groups, where the Makanin–Razborov algorithm can be applied. The technique of canonical representatives was later generalized by Dahmani to the case of relatively hyperbolic groups and played a key role in the solution of the isomorphism problem for "toral" relatively hyperbolic groups.
In his work on the isomorphism problem Sela also introduced and developed the notion of a JSJ-decomposition for word-hyperbolic groups, motivated by the notion of a JSJ decomposition for 3-manifolds. A JSJ-decomposition is a representation of a word-hyperbolic group as the fundamental group of a graph of groups which encodes in a canonical way all possible splittings over infinite cyclic subgroups. The idea of JSJ-decomposition was later extended by Rips and Sela to torsion-free finitely presented groups and this work gave rise a systematic development of the JSJ-decomposition theory with many further extensions and generalizations by other mathematicians. Sela applied a combination of his JSJ-decomposition and real tree techniques to prove that torsion-free word-hyperbolic groups are Hopfian. This result and Sela's approach were later generalized by others to finitely generated subgroups of hyperbolic groups and to the setting of relatively hyperbolic groups.
Sela's most important work came in early 2000s when he produced a solution to a famous Tarski conjecture. Namely, in a long series of papers, he proved that any two non-abelian finitely generated free groups have the same first-order theory. Sela's work relied on applying his earlier JSJ-decomposition and real tree techniques as well as developing new ideas and machinery of "algebraic geometry" over free groups.
Sela pushed this work further to study first-order theory of arbitrary torsion-free word-hyperbolic groups and to characterize all groups that are elementarily equivalent to (that is, have the same first-order theory as) a given torsion-free word-hyperbolic group. In particular, his work implies that if a finitely generated group "G" is elementarily equivalent to a word-hyperbolic group then "G" is word-hyperbolic as well.
Sela also proved that the first-order theory of a finitely generated free group is stable in the model-theoretic sense, providing a brand-new and qualitatively different source of examples for the stability theory.
An alternative solution for the Tarski conjecture has been presented by Olga Kharlampovich and Alexei Myasnikov.
The work of Sela on first-order theory of free and word-hyperbolic groups substantially influenced the development of geometric group theory, in particular by stimulating the development and the study of the notion of limit groups and of relatively hyperbolic groups.


Plancherel measure

In mathematics, Plancherel measure is a measure defined on the set of irreducible unitary representations of a locally compact group formula_1, that describes how the regular representation breaks up into irreducible unitary representations. In some cases the term Plancherel measure is applied specifically in the context of the group formula_1 being the finite symmetric group formula_3 – see below. It is named after the Swiss mathematician Michel Plancherel for his work in representation theory.
Definition for finite groups.
Let formula_1 be a finite group, we denote the set of its irreducible representations by formula_5. The corresponding Plancherel measure over the set formula_5 is defined by
where formula_8, and formula_9 denotes the dimension of the irreducible representation formula_10.
Definition on the symmetric group formula_3.
An important special case is the case of the finite symmetric group formula_3, where formula_13 is a positive integer. For this group, the set formula_14 of irreducible representations is in natural bijection with the set of integer partitions of formula_13. For an irreducible representation associated with an integer partition formula_16, its dimension is known to be equal to formula_17, the number of standard Young tableaux of shape formula_16, so in this case Plancherel measure is often thought of as a measure on the set of integer partitions of given order "n", given by
The fact that those probabilities sum up to 1 follows from the combinatorial identity
which corresponds to the bijective nature of the Robinson–Schensted correspondence.
Application.
Plancherel measure appears naturally in combinatorial and probabilistic problems, especially in the study of longest increasing subsequence of a random permutation formula_21. As a result of its importance in that area, in many current research papers the term Plancherel measure almost exclusively refers to the case of the symmetric group formula_3.
Connection to longest increasing subsequence.
Let formula_23 denote the length of a longest increasing subsequence of a random permutation formula_21 in formula_3 chosen according to the uniform distribution. Let formula_16 denote the shape of the corresponding Young tableaux related to formula_21 by the Robinson–Schensted correspondence. Then the following identity holds:
where formula_29 denotes the length of the first row of formula_16. Furthermore, from the fact that the Robinson–Schensted correspondence is bijective it follows that the distribution of formula_16 is exactly the Plancherel measure on formula_3. So, to understand the behavior of formula_23, it is natural to look at formula_29 with formula_16 chosen according to the Plancherel measure in formula_3, since these two random variables have the same probability distribution.
Poissonized Plancherel measure.
Plancherel measure is defined on formula_3 for each integer formula_13. In various studies of the asymptotic behavior of formula_23 as formula_40, it has proved useful to extend the measure to a measure, called the Poissonized Plancherel measure, on the set formula_41 of all integer partitions. For any formula_42, the Poissonized Plancherel measure with parameter formula_43 on the set formula_41 is defined by
for all formula_46.
Plancherel growth process.
The Plancherel growth process is a random sequence of Young diagrams formula_47 such that each formula_48 is a random Young diagram of order formula_13 whose probability distribution is the "n"th Plancherel measure, and each successive formula_48 is obtained from its predecessor formula_51 by the addition of a single box, according to the transition probability
for any given Young diagrams formula_53 and formula_16 of sizes "n" − 1 and "n", respectively.
So, the Plancherel growth process can be viewed as a natural coupling of the different Plancherel measures of all the symmetric groups, or alternatively as a random walk on Young's lattice. It is not difficult to show that the probability distribution of formula_48 in this walk coincides with the Plancherel measure on formula_3.
Compact groups.
The Plancherel measure for compact groups is similar to that for finite groups, except that the measure need not be finite. The unitary dual is a discrete set of finite-dimensional representations, and the Plancherel measure of an irreducible finite-dimensional representation is proportional to its dimension.
Abelian groups.
The unitary dual of a locally compact abelian group is another locally compact abelian group, and the Plancherel measure is proportional to the Haar measure of the dual group.
Semisimple Lie groups.
The Plancherel measure for semisimple Lie groups was found by Harish-Chandra. The support is the set of tempered representations, and in particular not all unitary representations need occur in the support.


Jacobi rotation

In numerical linear algebra, a Jacobi rotation is a rotation, "Q""k"ℓ, of a 2-dimensional linear subspace of an "n-"dimensional inner product space, chosen to zero a symmetric pair of off-diagonal entries of an "n"×"n" real symmetric matrix, "A", when applied as a similarity transformation:
It is the core operation in the Jacobi eigenvalue algorithm, which is numerically stable and well-suited to implementation on parallel processors .
Only rows "k" and ℓ and columns "k" and ℓ of "A" will be affected, and that "A"′ will remain symmetric. Also, an explicit matrix for "Q""k"ℓ is rarely computed; instead, auxiliary values are computed and "A" is updated in an efficient and numerically stable way. However, for reference, we may write the matrix as
That is, "Q""k"ℓ is an identity matrix except for four entries, two on the diagonal ("q""kk" and "q"ℓℓ, both equal to "c") and two symmetrically placed off the diagonal ("q""k"ℓ and "q"ℓ"k", equal to "s" and −"s", respectively). Here "c" = cos ϑ and "s" = sin ϑ for some angle ϑ; but to apply the rotation, the angle itself is not required. Using Kronecker delta notation, the matrix entries can be written
Suppose "h" is an index other than "k" or ℓ (which must themselves be distinct). Then the similarity update produces, algebraically,
Numerically stable computation.
To determine the quantities needed for the update, we must solve the off-diagonal equation for zero . This implies that
Set β to half of this quantity,
If "a""k"ℓ is zero we can stop without performing an update, thus we never divide by zero. Let "t" be tan ϑ. Then with a few trigonometric identities we reduce the equation to
For stability we choose the solution
From this we may obtain "c" and "s" as
Although we now could use the algebraic update equations given previously, it may be preferable to rewrite them. Let
so that ρ = tan(ϑ/2). Then the revised update equations are
As previously remarked, we need never explicitly compute the rotation angle ϑ. In fact, we can reproduce the symmetric update determined by "Q""k"ℓ by retaining only the three values "k", ℓ, and "t", with "t" set to zero for a null rotation.


Pre-abelian category

In mathematics, specifically in category theory, a pre-abelian category is an additive category that has all kernels and cokernels.
Spelled out in more detail, this means that a category C is pre-abelian if:
Note that the zero morphism in item 3 can be identified as the identity element of the hom-set Hom("A","B"), which is an abelian group by item 1; or as the unique morphism "A" → 0 → "B", where 0 is a zero object, guaranteed to exist by item 2.
Examples.
The original example of an additive category is the category Ab of abelian groups.
Ab is preadditive because it is a closed monoidal category, the biproduct in Ab is the finite direct sum, the kernel is inclusion of the ordinary kernel from group theory and the cokernel is the quotient map onto the ordinary cokernel from group theory.
Other common examples:
These will give you an idea of what to think of; for more examples, see abelian category (every abelian category is pre-abelian).
Elementary properties.
Every pre-abelian category is of course an additive category, and many basic properties of these categories are described under that subject. This article concerns itself with the properties that hold specifically because of the existence of kernels and cokernels.
Although kernels and cokernels are special kinds of equalisers and coequalisers, a pre-abelian category actually has "all" equalisers and coequalisers.
We simply construct the equaliser of two morphisms "f" and "g" as the kernel of their difference "g" − "f"; similarly, their coequaliser is the cokernel of their difference.
Since pre-abelian categories have all finite products and coproducts (the biproducts) and all binary equalisers and coequalisers (as just described), then by a general theorem of category theory, they have all finite limits and colimits.
That is, pre-abelian categories are finitely complete.
The existence of both kernels and cokernels gives a notion of image and coimage.
We can define these as
That is, the image is the kernel of the cokernel, and the coimage is the cokernel of the kernel.
Note that this notion of image may not correspond to the usual notion of image, or range, of a function, even assuming that the morphisms in the category "are" functions.
For example, in the category of topological abelian groups, the image of a morphism actually corresponds to the inclusion of the "closure" of the range of the function.
For this reason, people will often distinguish the meanings of the two terms in this context, using "image" for the abstract categorical concept and "range" for the elementary set-theoretic concept.
In many common situations, such as the category of sets, where images and coimages exist, their objects are isomorphic.
Put more precisely, we have a factorisation of "f": "A" → "B" as
where the morphism on the left is the coimage, the morphism on the right is the image, and the morphism in the middle (called the "parallel" of "f") is an isomorphism.
In a pre-abelian category, "this is not necessarily true".
The factorisation shown above does always exist, but the parallel might not be an isomorphism.
In fact, the parallel of "f" is an isomorphism for every morphism "f" if and only if the pre-abelian category is an abelian category.
An example of a non-abelian, pre-abelian category is, once again, the category of topological abelian groups.
As remarked, the image is the inclusion of the "closure" of the range; however, the coimage is a quotient map onto the range itself.
Thus, the parallel is the inclusion of the range into its closure, which is not an isomorphism unless the range was already closed.
Exact functors.
Recall that all finite limits and colimits exist in a pre-abelian category.
In general category theory, a functor is called "left exact" if it preserves all finite limits and "right exact" if it preserves all finite colimits. (A functor is simply "exact" if it's both left exact and right exact.)
In a pre-abelian category, exact functors can be described in particularly simple terms.
First, recall that an additive functor is a functor "F": C → D between preadditive categories that acts as a group homomorphism on each hom-set.
Then it turns out that a functor between pre-abelian categories is left exact if and only if it is additive and preserves all kernels, and it's right exact if and only if it's additive and preserves all cokernels.
Note that an exact functor, because it preserves both kernels and cokernels, preserves all images and coimages.
Exact functors are most useful in the study of abelian categories, where they can be applied to exact sequences.
Maximal exact structure.
On every pre-abelian category formula_1 there exists an exact structure formula_2 that is maximal in the sense that it contains every other exact structure. The exact structure formula_2 consists of precisely those kernel-cokernel pairs formula_4 where formula_5 is a semi-stable kernel and formula_6 is a semi-stable cokernel. Here, formula_7 is a semi-stable kernel if it is a kernel and for each morphism formula_8 in the pushout diagram
formula_9
the morphism formula_10 is again a kernel. formula_11 is a semi-stable cokernel if it is a cokernel and for every morphism formula_12 in the pullback diagram
formula_13
the morphism formula_14 is again a cokernel.
A pre-abelian category formula_1 is quasi-abelian if and only if all kernel-cokernel pairs form an exact structure. An example for which this is not the case is the category of (Hausdorff) bornological spaces.
The result is also valid for additive categories that are not pre-abelian but Karoubian.
Special cases.
The pre-abelian categories most commonly studied are in fact abelian categories; for example, Ab is an abelian category. Pre-abelian categories that are not abelian appear for instance in functional analysis.


Kuga fiber variety

In algebraic geometry, a Kuga fiber variety, introduced by , is a fiber space whose fibers are abelian varieties and whose base space is an arithmetic quotient of a Hermitian symmetric space.


Pseudo-Zernike polynomials

In mathematics, pseudo-Zernike polynomials are well known and widely used in the analysis of optical systems. They are also widely used in image analysis as shape descriptors.
Definition.
They are an orthogonal set of complex-valued polynomials
defined as
where formula_2 and orthogonality on the unit disk is given as
where the star means complex conjugation, and
formula_4, formula_5, formula_6
are the standard transformations between polar and Cartesian coordinates.
The radial polynomials formula_7 are defined as
formula_8
with integer coefficients
Examples.
Examples are:
formula_10
formula_11
formula_12
formula_13
formula_14
formula_15
formula_16
formula_17
formula_18
formula_19
formula_20
formula_21
formula_22
formula_23
formula_24
formula_25
formula_26
formula_27
formula_28
formula_29
formula_30
Moments.
The pseudo-Zernike Moments (PZM) of order formula_31 and repetition formula_32 are defined as
where formula_34, and formula_32 takes on positive and negative integer
values subject to formula_36.
The image function can be reconstructed by expansion of the pseudo-Zernike coefficients on the unit disk as
Pseudo-Zernike moments are derived from conventional Zernike moments and shown
to be more robust and less sensitive to image noise than the Zernike moments.


Frank-Olaf Schreyer

Frank-Olaf Schreyer is a German mathematician, specializing in algebraic geometry and algorithmic algebraic geometry.
Schreyer received in 1983 his PhD from Brandeis University with thesis "Syzgies of Curves with Special Pencils" under the supervision of David Eisenbud. Schreyer was a professor at University of Bayreuth and is since 2002 a professor at Saarland University.
He is involved in the development of (algorithmic) algebraic geometry advanced by David Eisenbud. Much of Schreyer's research deals with syzygy theory and the development of algorithms for the calculation of syzygies.
In 2010 he was an invited speaker (jointly with David Eisenbud) at the International Congress of Mathematicians in Hyderabad. In 2012 he was elected a Fellow of the American Mathematical Society.


Duplication and elimination matrices

In mathematics, especially in linear algebra and matrix theory, the duplication matrix and the elimination matrix are linear transformations used for transforming half-vectorizations of matrices into vectorizations or (respectively) vice versa.
Duplication matrix.
The duplication matrix formula_1 is the unique formula_2 matrix which, for any formula_3 symmetric matrix formula_4, transforms formula_5 into formula_6:
For the formula_8 symmetric matrix formula_9, this transformation reads
The explicit formula for calculating the duplication matrix for a formula_11 matrix is:
formula_12
Where:
Elimination matrix.
An elimination matrix formula_21 is a formula_22 matrix which, for any formula_11 matrix formula_24, transforms formula_6 into formula_5:
For the formula_28 matrix formula_29, one choice for this transformation is given by


H4 (mathematics)


Michael Vaughan-Lee

Michael Rogers Vaughan-Lee is a mathematician and retired academic. He was Professor of Mathematics at the University of Oxford from 1996 to 2010 and a tutor at Christ Church, Oxford, between 1971 and 2010.
Career.
Vaughan-Lee completed his Doctor of Philosophy (DPhil) degree at the University of Oxford in 1968 and then taught at Vanderbilt University for two years as an assistant professor. In 1970, he was appointed to a lectureship at the University of Queensland, but resigned the following year and returned to the United Kingdom to become a tutor in mathematics at Christ Church, Oxford, where he remained until he retired in 2010. In 1996, he was awarded the title of Professor of Mathematics by the University of Oxford; since retirement in 2010, he has been an emeritus professor.
Research.
Vaughan-Lee specialises in group theory, especially the restricted Burnside problem. He has also made contributions relating to Engel Lie algebras, computational algebra, and other areas.


Principalization (algebra)

In the mathematical field of algebraic number theory, the concept of principalization refers to a situation when, given an extension of algebraic number fields, some ideal (or more generally fractional ideal) of the ring of integers of the smaller field isn't principal but its extension to the ring of integers of the larger field is. Its study has origins in the work of Ernst Kummer on ideal numbers from the 1840s, who in particular proved that for every algebraic number field there exists an extension number field such that all ideals of the ring of integers of the base field (which can always be generated by at most two elements) become principal when extended to the larger field. In 1897 David Hilbert conjectured that the maximal abelian unramified extension of the base field, which was later called the Hilbert class field of the given base field, is such an extension. This conjecture, now known as principal ideal theorem, was proved by Philipp Furtwängler in 1930 after it had been translated from number theory to group theory by Emil Artin in 1929, who made use of his general reciprocity law to establish the reformulation. Since this long desired proof was achieved by means of Artin transfers of non-abelian groups with derived length two, several investigators tried to exploit the theory of such groups further to obtain additional information on the principalization in intermediate fields between the base field and its Hilbert class field. The first contributions in this direction are due to Arnold Scholz and Olga Taussky in 1934, who coined the synonym capitulation for principalization. Another independent access to the principalization problem via Galois cohomology of unit groups is also due to Hilbert and goes back to the chapter on cyclic extensions of number fields of prime degree in his number report, which culminates in the famous Theorem 94.
Extension of classes.
Let formula_1 be an algebraic number field, called the "base field", and let formula_2 be a field extension of finite degree. Let formula_3 and formula_4 denote the ring of integers, the group of nonzero fractional ideals and its subgroup of principal fractional ideals of the fields formula_5 respectively. Then the extension map of fractional ideals
is an injective group homomorphism. Since formula_7, this map induces the extension homomorphism of ideal class groups
If there exists a non-principal ideal formula_9 (i.e. formula_10) whose extension ideal in formula_11 is principal (i.e. formula_12 for some formula_13 and formula_14), then we speak about principalization or capitulation in formula_2. In this case, the ideal formula_16 and its class formula_17 are said to principalize or capitulate in formula_11. This phenomenon is described most conveniently by the principalization kernel or capitulation kernel, that is the kernel formula_19 of the class extension homomorphism.
More generally, let formula_20 be a modulus in formula_1, where formula_22 is a nonzero ideal in formula_23 and formula_24 is a formal product of pair-wise different real infinite primes of formula_1. Then
is the ray modulo formula_27, where formula_28 is the group of nonzero fractional ideals in formula_1 relatively prime to formula_22 and the condition formula_31 means formula_32 and formula_33 for every real infinite prime formula_34 dividing formula_35 Let formula_36 then the group formula_37 is called a generalized ideal class group for formula_38 If formula_39 and formula_40 are generalized ideal class groups such that formula_41 for every formula_42 and formula_43 for every formula_44, then formula_45 induces the extension homomorphism of generalized ideal class groups:
Galois extensions of number fields.
Let formula_47 be a Galois extension of algebraic number fields with Galois group formula_48 and let formula_49 denote the set of prime ideals of the fields formula_50 respectively. Suppose that formula_51 is a prime ideal of formula_1 which does not divide the relative discriminant formula_53, and is therefore unramified in formula_54, and let formula_55 be a prime ideal of formula_54 lying over formula_57.
Frobenius automorphism.
There exists a unique automorphism formula_58 such that formula_59 for all algebraic integers formula_60, where formula_61 is the norm of formula_57. The map formula_63 is called the Frobenius automorphism of formula_64. It generates the decomposition group formula_65 of formula_64 and its order is equal to the inertia degree formula_67 of formula_64 over formula_57. (If formula_57 is ramified then formula_71 is only defined and generates formula_72 modulo the inertia subgroup
whose order is the ramification index formula_74 of formula_64 over formula_57). Any other prime ideal of formula_54 dividing formula_57 is of the form formula_79 with some formula_80. Its Frobenius automorphism is given by
since
for all formula_60, and thus its decomposition group formula_84 is conjugate to formula_72. In this general situation, the Artin symbol is a mapping
which associates an entire conjugacy class of automorphisms to any unramified prime ideal formula_87, and we have formula_88 if and only if formula_57 splits completely in formula_54.
Factorization of prime ideals.
When formula_91 is an intermediate field with relative Galois group formula_92, more precise statements about the homomorphisms formula_45 and formula_94 are possible because we can construct the factorization of formula_57 (where formula_57 is unramified in formula_54 as above) in formula_98 from its factorization in formula_99 as follows. Prime ideals in formula_99 lying over formula_57 are in formula_102-equivariant bijection with the formula_102-set of left cosets formula_104, where formula_79 corresponds to the coset formula_106. For every prime ideal formula_107 in formula_98 lying over formula_57 the Galois group formula_110 acts transitively on the set of prime ideals in formula_99 lying over formula_107, thus such ideals formula_107 are in bijection with the orbits of the action of formula_110 on formula_104 by left multiplication. Such orbits are in turn in bijection with the double cosets formula_116. Let formula_117 be a complete system of representatives of these double cosets, thus formula_118. Furthermore, let formula_119 denote the orbit of the coset formula_120 in the action of formula_110 on the set of left cosets formula_104 by left multiplication and let formula_123 denote the orbit of the coset formula_124 in the action of formula_72 on the set of right cosets formula_126 by right multiplication. Then formula_57 factorizes in formula_98 as formula_129, where formula_130 for formula_131 are the prime ideals lying over formula_57 in formula_11 satisfying formula_134 with the product running over any system of representatives of formula_119.
We have
Let formula_137 be the decomposition group of formula_138 over formula_11. Then formula_140 is the stabilizer of formula_120 in the action of formula_110 on formula_104, so by the orbit-stabilizer theorem we have formula_144. On the other hand, it's formula_145, which together gives
In other words, the inertia degree formula_147 is equal to the size of the orbit of the coset formula_124 in the action of formula_71 on the set of right cosets formula_126 by right multiplication. By taking inverses, this is equal to the size of the orbit formula_151 of the coset formula_152 in the action of formula_71 on the set of left cosets formula_154 by left multiplication. Also the prime ideals in formula_98 lying over formula_57 correspond to the orbits of this action.
Consequently, the ideal embedding is given by formula_157, and the class extension by
Artin's reciprocity law.
Now further assume formula_47 is an abelian extension, that is, formula_102 is an abelian group. Then, all conjugate decomposition groups of prime ideals of formula_54 lying over formula_57 coincide, thus formula_163 for every formula_80, and the Artin symbol formula_165 becomes equal to the Frobenius automorphism of any formula_166 and formula_167 for all formula_60 and every formula_166.
By class field theory,
the abelian extension formula_47 uniquely corresponds to an intermediate group formula_171 between the ray modulo formula_172 of formula_1 and formula_174, where formula_175 denotes the relative conductor (formula_176 is divisible by the same prime ideals as formula_177). The Artin symbol
which associates the Frobenius automorphism of formula_57 to each prime ideal formula_57 of formula_1 which is unramified in formula_54, can be extended by multiplicativity to a surjective homomorphism
with kernel formula_184 (where formula_185 means formula_186), called Artin map, which induces isomorphism
of the generalized ideal class group formula_188 to the Galois group formula_102. This explicit isomorphism is called the Artin reciprocity law or "general reciprocity law".
Group-theoretic formulation of the problem.
This reciprocity law allowed Artin to translate the general principalization problem for number fields formula_91 based on the following scenario from number theory to group theory. Let formula_47 be a Galois extension of algebraic number fields with automorphism group formula_48. Assume that formula_91 is an intermediate field with relative group formula_194 and let formula_195 be the maximal abelian subextension of formula_196 respectively within formula_54. Then the corresponding relative groups are the commutator subgroups formula_198, resp. formula_199. By class field theory, there exist intermediate groups formula_200 and formula_201 such that the Artin maps establish isomorphisms
Here formula_203 means formula_204 and formula_205 are some moduli divisible by formula_206 respectively and by all primes dividing formula_207 respectively.
The ideal extension homomorphism formula_208, the induced Artin transfer formula_209 and these Artin maps are connected by the formula
Since formula_211 is generated by the prime ideals of formula_1 which does not divide formula_177, it's enough to verify this equality on these generators. Hence suppose that formula_214 is a prime ideal of formula_1 which does not divide formula_177 and let formula_217 be a prime ideal of formula_54 lying over formula_57. On the one hand, the ideal extension homomorphism formula_45 maps the ideal formula_57 of the base field formula_1 to the extension ideal formula_223 in the field formula_11, and the Artin map formula_225 of the field formula_11 maps this product of prime ideals to the product of conjugates of Frobenius automorphisms
where the double coset decomposition and its representatives used here is the same as in the last but one section. On the other hand, the Artin map formula_228 of the base field formula_1 maps the ideal formula_57 to the Frobenius automorphism formula_231. The formula_232-tuple formula_233 is a system of representatives of double cosets formula_234, which correspond to the orbits of the action of formula_71 on the set of left cosets formula_154 by left multiplication, and formula_237 is equal to the size of the orbit of coset formula_152 in this action. Hence the induced Artin transfer maps formula_239 to the product
This product expression was the original form of the Artin transfer homomorphism, corresponding to a decomposition of the permutation representation into disjoint cycles.
Since the kernels of the Artin maps formula_241 and formula_242 are formula_243 and formula_244 respectively, the previous formula implies that formula_245. It follows that there is the class extension homomorphism formula_246 and that formula_94 and the induced Artin transfer formula_209 are connected by the commutative diagram in Figure 1 via the isomorphisms induced by the Artin maps, that is, we have equality of two composita formula_249.
Class field tower.
The commutative diagram in the previous section, which connects the number theoretic class extension homomorphism formula_94 with the group theoretic Artin transfer formula_251, enabled Furtwängler to prove the principal ideal theorem by specializing to the situation that formula_252 is the (first) Hilbert class field of formula_1, that is the maximal abelian unramified extension of formula_1, and formula_255 is the "second Hilbert class field" of formula_1, that is the maximal metabelian unramified extension of formula_1 (and maximal abelian unramified extension of formula_258). Then formula_259 and formula_260 is the commutator subgroup of formula_102. More precisely, Furtwängler showed that generally the Artin transfer formula_262 from a finite metabelian group formula_102 to its derived subgroup formula_264 is a trivial homomorphism. In fact this is true even if formula_102 isn't metabelian because we can reduce to the metabelian case by replacing formula_102 with formula_267. It also holds for infinite groups provided formula_102 is finitely generated and formula_269. It follows that every ideal of formula_1 extends to a principal ideal of formula_258.
However, the commutative diagram comprises the potential for a lot of more sophisticated applications. In the situation that formula_272 is a prime number, formula_273 is the "second Hilbert p-class field" of formula_1, that is the maximal metabelian unramified extension of formula_1 of degree a power of formula_276 varies over the intermediate field between formula_1 and its first "Hilbert p-class" field formula_278, and formula_279 correspondingly varies over the intermediate groups between formula_102 and formula_264, computation of all principalization kernels formula_19 and all "p-class groups" formula_283 translates to information on the kernels formula_284 and targets formula_285 of the Artin transfers formula_251 and permits the exact specification of the "second p-class group" formula_287 of formula_1 via pattern recognition, and frequently even allows to draw conclusions about the entire "p-class field tower" of formula_1, that is the Galois group formula_290 of the maximal unramified pro-"p" extension formula_291 of formula_1.
These ideas are explicit in the paper of 1934 by A. Scholz and O. Taussky already. At these early stages, "pattern recognition" consisted of specifying the "annihilator ideals", or "symbolic orders", and the "Schreier relations" of metabelian "p"-groups and subsequently using a uniqueness theorem on group extensions by O. Schreier.
Nowadays, we use the "p"-group generation algorithm of M. F. Newman
and E. A. O'Brien
for constructing descendant trees of "p"-groups and searching patterns, defined by kernels and targets of Artin transfers, among the vertices of these trees.
Galois cohomology.
In the chapter on cyclic extensions of number fields of prime degree of his number report from 1897, D. Hilbert
proves a series of crucial theorems which culminate in Theorem 94, the original germ of class field theory. Today, these theorems can be viewed as the beginning of what is now called Galois cohomology. Hilbert considers a finite relative extension formula_2 of algebraic number fields with cyclic Galois group formula_294 generated by an automorphism formula_295 such that formula_296 for the relative degree formula_297, which is assumed to be an odd prime.
He investigates two endomorphism of the unit group formula_298 of the extension field, viewed as a Galois module with respect to the group formula_102, briefly a formula_102-module. The first endomorphism
is the symbolic exponentiation with the difference formula_302, and the second endomorphism
is the "algebraic norm" mapping, that is the symbolic exponentiation with the trace
In fact, the image of the algebraic norm map is contained in the unit group formula_305 of the base field and formula_306 coincides with the usual arithmetic (field) norm as the product of all conjugates. The composita of the endomorphisms satisfy the relations formula_307 and formula_308.
Two important cohomology groups can be defined by means of the kernels and images of these endomorphisms. The zeroth Tate cohomology group of formula_102 in formula_310 is given by the quotient formula_311 consisting of the "norm residues" of formula_305, and the minus first Tate cohomology group of formula_102 in formula_310 is given by the quotient formula_315 of the group formula_316 of "relative units" of formula_2 modulo the subgroup of symbolic powers of units with formal exponent formula_318.
In his Theorem 92 Hilbert proves the existence of a relative unit formula_319 which cannot be expressed as formula_320, for any unit formula_321, which means that the minus first cohomology group formula_322 is non-trivial of order divisible by formula_323. However, with the aid of a completely similar construction, the minus first cohomology group formula_324 of the formula_102-module formula_326, the multiplicative group of the superfield formula_11, can be defined, and Hilbert shows its triviality formula_328 in his famous Theorem 90.
Eventually, Hilbert is in the position to state his celebrated Theorem 94: If formula_2 is a cyclic extension of number fields of odd prime degree formula_323 with trivial relative discriminant formula_331, which means it's unramified at finite primes, then there exists a non-principal ideal formula_332 of the base field formula_1 which becomes principal in the extension field formula_11, that is formula_335 for some formula_13. Furthermore, the formula_323th power of this non-principal ideal is principal in the base field formula_1, in particular formula_339, hence the class number of the base field must be divisible by formula_323 and the extension field formula_11 can be called a class field of formula_1. The proof goes as follows: Theorem 92 says there exists unit formula_343, then Theorem 90 ensures the existence of a (necessarily non-unit) formula_344 such that formula_345, i. e., formula_346. By multiplying formula_347 by proper integer if necessary we may assume that formula_347 is an algebraic integer. The non-unit formula_347 is generator of an "ambiguous" principal ideal of formula_2, since formula_351. However, the underlying ideal formula_352 of the subfield formula_1 cannot be principal. Assume to the contrary that formula_354 for some formula_355. Since formula_2 is unramified, every ambiguous ideal formula_16 of formula_98 is a lift of some ideal in formula_23, in particular formula_360. Hence formula_361 and thus formula_362 for some unit formula_321. This would imply the contradiction formula_364 because formula_365. On the other hand,
thus formula_367 is principal in the base field formula_1 already.
Theorems 92 and 94 don't hold as stated for formula_369, with the fields formula_370 and formula_371 being a counterexample (in this particular case formula_11 is the narrow Hilbert class field of formula_1). The reason is Hilbert only considers ramification at finite primes but not at infinite primes (we say that a real infinite prime of formula_1 ramifies in formula_11 if there exists non-real extension of this prime to formula_11). This doesn't make a difference when formula_377 is odd since the extension is then unramified at infinite primes. However he notes that Theorems 92 and 94 hold for formula_369 provided we further assume that number of fields conjugate to formula_11 that are real is twice the number of real fields conjugate to formula_1. This condition is equivalent to formula_2 being unramified at infinite primes, so Theorem 94 holds for all primes formula_323 if we assume that formula_2 is unramified everywhere.
Theorem 94 implies the simple inequality formula_384 for the order of the principalization kernel of the extension formula_2. However an exact formula for the order of this kernel can be derived for cyclic unramified (including infinite primes) extension (not necessarily of prime degree) by means of the Herbrand quotient formula_386 of the formula_102-module formula_310, which is given by
It can be shown that formula_390 (without calculating the order of either of the cohomology groups). Since the extension formula_2 is unramified, it's formula_392 so formula_393 . With the aid of K. Iwasawa's isomorphism
formula_394, specialized to a cyclic extension with periodic cohomology of length formula_395, we obtain
This relation increases the lower bound by the factor formula_397, the so-called "unit norm index".
History.
As mentioned in the lead section, several investigators tried to generalize the Hilbert-Artin-Furtwängler principal ideal theorem of 1930 to questions concerning the principalization in intermediate extensions between the base field and its Hilbert class field. On the one hand, they established general theorems on the principalization over arbitrary number fields, such as Ph. Furtwängler 1932,
O. Taussky 1932,
O. Taussky 1970,
and H. Kisilevsky 1970.
On the other hand, they searched for concrete numerical examples of principalization in unramified cyclic extensions of particular kinds of base fields.
Quadratic fields.
The principalization of formula_398-classes of imaginary quadratic fields formula_399 with formula_398-class rank two in unramified cyclic cubic extensions was calculated manually for three discriminants formula_401 by A. Scholz and O. Taussky
in 1934. Since these calculations require composition of binary quadratic forms and explicit knowledge of fundamental systems of units in cubic number fields, which was a very difficult task in 1934, the investigations stayed at rest for half a century until F.-P. Heider and B. Schmithals
employed the CDC Cyber 76 computer at the University of Cologne to extend the information concerning principalization to the range formula_402 containing formula_403 relevant discriminants in 1982,
thereby providing the first analysis of five real quadratic fields.
Two years later, J. R. Brink
computed the principalization types of formula_404 complex quadratic fields.
Currently, the most extensive computation of principalization data for all formula_405 quadratic fields with discriminants formula_406 and formula_398-class group of type formula_408 is due to D. C. Mayer in 2010,
who used his recently discovered connection between transfer kernels and transfer targets for the design of a new "principalization algorithm".
The formula_395-principalization in unramified quadratic extensions of imaginary quadratic fields with formula_395-class group of type formula_411 was studied by H. Kisilevsky in 1976.
Similar investigations of real quadratic fields were carried out by E. Benjamin and C. Snyder in 1995.
Cubic fields.
The formula_395-principalization in unramified quadratic extensions of cyclic cubic fields with formula_395-class group of type formula_411 was investigated by A. Derhem in 1988.
Seven years later, M. Ayadi studied the formula_398-principalization in unramified cyclic cubic extensions of cyclic cubic fields formula_416, formula_417, with formula_398-class group of type formula_408 and conductor formula_420 divisible by two or three primes.
Sextic fields.
In 1992, M. C. Ismaili investigated the formula_398-principalization in unramified cyclic cubic extensions of the normal closure of pure cubic fields formula_422, in the case that this sextic number field formula_423, formula_424, has a formula_398-class group of type formula_408.
Quartic fields.
In 1993, A. Azizi studied the formula_395-principalization in unramified quadratic extensions of biquadratic fields of "Dirichlet type" formula_428 with formula_395-class group of type formula_411. Most recently, in 2014, A. Zekhnini extended the investigations to Dirichlet fields with formula_395-class group of type formula_432, thus providing the first examples of formula_395-principalization in the two layers of unramified quadratic and biquadratic extensions of quartic fields with class groups of formula_395-rank three.
See also.
Both, the algebraic, group theoretic access to the principalization problem by Hilbert-Artin-Furtwängler and the arithmetic, cohomological access by Hilbert-Herbrand-Iwasawa are also presented in detail in the two "bibles of capitulation" by J.-F. Jaulent 1988 and by K. Miyake 1989.


Drinfeld module

In mathematics, a Drinfeld module (or elliptic module) is roughly a special kind of module over a ring of functions on a curve over a finite field, generalizing the Carlitz module. Loosely speaking, they provide a function field analogue of complex multiplication theory. A shtuka (also called F-sheaf or chtouca) is a sort of generalization of a Drinfeld module, consisting roughly of a vector bundle over a curve, together with some extra structure identifying a "Frobenius twist" of the bundle with a "modification" of it.
Drinfeld modules were introduced by , who used them to prove the Langlands conjectures for GL2 of an algebraic function field in some special cases. He later invented shtukas and used shtukas of rank 2 to prove
the remaining cases of the Langlands conjectures for GL2. Laurent Lafforgue proved the Langlands conjectures for GL"n" of a function field by studying the moduli stack of shtukas of rank "n".
"Shtuka" is a Russian word штука meaning "a single copy", which comes from the German noun “Stück”, meaning “piece, item, or unit". In Russian, the word "shtuka" is also used in slang for a thing with known properties, but having no name in a speaker's mind.
Drinfeld modules.
The ring of additive polynomials.
We let formula_1 be a field of characteristic formula_2. The ring formula_3 is defined to be the ring of "noncommutative" (or twisted) polynomials formula_4 over formula_1, with the multiplication given by
The element formula_7 can be thought of as a Frobenius element: in fact, formula_1 is a left module over formula_3, with elements of formula_1 acting as multiplication and formula_7 acting as the Frobenius endomorphism of formula_1. The ring formula_3 can also be thought of as the ring of all (absolutely) additive polynomials
in formula_15, where a polynomial formula_16 is called "additive" if formula_17 (as elements of formula_18). The ring of additive polynomials is generated as an algebra over formula_1 by the polynomial formula_20. The multiplication in the ring of additive polynomials is given by composition of polynomials, not by multiplication of commutative polynomials, and is not commutative.
Definition of Drinfeld modules.
Let "F" be an algebraic function field with a finite field of constants and fix a place formula_21 of "F". Define "A" to be the ring of elements in "F" that are regular at every place except possibly formula_21. In particular, "A" is a Dedekind domain and it is discrete in "F" (with the topology induced by formula_21). For example, we may take "A" to be the polynomial ring formula_24. Let "L" be a field equipped with a ring homomorphism formula_25.
The condition that the image of "A" is not in "L" is a non-degeneracy condition, put in to eliminate trivial cases, while the condition that formula_30 gives the impression that a Drinfeld module is simply a deformation of the map formula_27.
As "L"{τ} can be thought of as endomorphisms of the additive group of "L", a Drinfeld "A"-module can be regarded as an action of "A" on the additive group of "L", or in other words as an "A"-module whose underlying additive group is the additive group of "L".
Shtukas.
Suppose that "X" is a curve over the finite field F"p".
A (right) shtuka of rank "r" over a scheme (or stack) "U" is given by the following data:
whose cokernels are supported on certain graphs of morphisms from "U" to "X" (called the zero and pole of the shtuka, and usually denoted by 0 and ∞), and are locally free of rank 1 on their supports. Here (Fr×1)*"E" is the pullback of "E" by the Frobenius endomorphism of "U".
A left shtuka is defined in the same way except that the direction of the morphisms is reversed. If the pole and zero of the shtuka are disjoint then left shtukas and right shtukas are essentially the same.
By varying "U", we get an algebraic stack "Shtukar" of shtukas of rank "r", a "universal" shtuka over "Shtukar"×"X" and a morphism (∞,0) from "Shtukar" to "X"×"X" which is smooth and of relative dimension 2"r" − 2. The stack "Shtukar" is not of finite type for "r" > 1.
Drinfeld modules are in some sense special kinds of shtukas. (This is not at all obvious from the definitions.) More precisely, Drinfeld showed how to construct a shtuka from a Drinfeld module.
See Drinfeld, V. G. "Commutative subrings of certain noncommutative rings." Funkcional. Anal. i Prilovzen. 11 (1977), no. 1, 11–14, 96. for details.
Applications.
The Langlands conjectures for function fields state (very roughly) that there is a bijection between cuspidal automorphic representations of "GL""n" and certain representations of a Galois group. Drinfeld used Drinfeld modules to prove some special cases of the Langlands conjectures, and later proved the full Langlands conjectures for "GL""2" by generalizing Drinfeld modules to shtukas.
The "hard" part of proving these conjectures is to construct Galois representations with certain properties, and Drinfeld constructed the necessary Galois representations by finding them inside the "l"-adic cohomology of certain moduli spaces of rank 2 shtukas.
Drinfeld suggested that moduli spaces of shtukas of rank "r" could be used in a similar way to prove the Langlands conjectures for "GL""r"; the formidable technical problems involved in carrying out this program were solved by Lafforgue after many years of effort.


Gaussian period

In mathematics, in the area of number theory, a Gaussian period is a certain kind of sum of roots of unity. The periods permit explicit calculations in cyclotomic fields connected with Galois theory and with harmonic analysis (discrete Fourier transform). They are basic in the classical theory called cyclotomy. Closely related is the Gauss sum, a type of exponential sum which is a linear combination of periods.
History.
As the name suggests, the periods were introduced by Gauss and were the basis for his theory of compass and straightedge construction. For example, the construction of the heptadecagon (a formula that furthered his reputation) depended on the algebra of such periods, of which
is an example involving the seventeenth root of unity
General definition.
Given an integer "n" > 1, let "H" be any subgroup of the multiplicative group
of invertible residues modulo "n", and let
A Gaussian period "P" is a sum of the primitive n-th roots of unity formula_5, where formula_6 runs through all of the elements in a fixed coset of "H" in "G".
The definition of "P" can also be stated in terms of the field trace. We have
for some subfield "L" of Q(ζ) and some "j" coprime to "n". This corresponds to the previous definition by identifying "G" and "H" with the Galois groups of Q(ζ)/Q and Q(ζ)/"L", respectively. The choice of "j" determines the choice of coset of "H" in "G" in the previous definition.
Example.
The situation is simplest when "n" is a prime number "p" > 2. In that case "G" is cyclic of order "p" − 1, and has one subgroup "H" of order "d" for every factor "d" of "p" − 1. For example, we can take "H" of index two. In that case "H" consists of the quadratic residues modulo "p". Corresponding to this "H" we have the Gaussian period
summed over ("p" − 1)/2 quadratic residues, and the other period "P*" summed over the ("p" − 1)/2 quadratic non-residues. It is easy to see that
since the left-hand side adds all the primitive "p"-th roots of 1. We also know, from the trace definition, that "P" lies in a quadratic extension of Q. Therefore, as Gauss knew, "P" satisfies a quadratic equation with integer coefficients. Evaluating the square of the sum "P" is connected with the problem of counting how many quadratic residues between 1 and "p" − 1 are succeeded by quadratic residues. The solution is elementary (as we would now say, it computes a local zeta-function, for a curve that is a conic). One has
This therefore gives us the precise information about which quadratic field lies in Q(ζ). (That could be derived also by ramification arguments in algebraic number theory; see quadratic field.)
As Gauss eventually showed, to evaluate "P" − "P"*, the correct square root to take is the positive (resp. "i" times positive real) one, in the two cases. Thus the explicit value of the period "P" is given by
Gauss sums.
As is discussed in more detail below, the Gaussian periods are closely related to another class of sums of roots of unity, now generally called Gauss sums (sometimes Gaussian sums). The quantity "P" − "P"* presented above is a quadratic Gauss sum mod "p", the simplest non-trivial example of a Gauss sum. One observes that "P" − "P"* may also be written as
where formula_12 here stands for the Legendre symbol ("a"/"p"), and the sum is taken over residue classes modulo "p". More generally, given a Dirichlet character χ mod "n", the Gauss sum mod "n" associated with χ is
For the special case of formula_14 the principal Dirichlet character, the Gauss sum reduces to the Ramanujan sum:
where μ is the Möbius function.
The Gauss sums formula_16 are ubiquitous in number theory; for example they occur significantly in the functional equations of L-functions. (Gauss sums are in a sense the finite field analogues of the gamma function.)
Relationship of Gaussian periods and Gauss sums.
The Gaussian periods are related to the Gauss sums formula_17 for which the character χ is trivial on "H". Such χ take the same value at all elements "a" in a fixed coset of "H" in "G". For example, the quadratic character mod "p" described above takes the value 1 at each quadratic residue, and takes the value -1 at each quadratic non-residue.
The Gauss sum formula_17 can thus be written as a linear combination of Gaussian periods (with coefficients χ("a")); the converse is also true, as a consequence of the orthogonality relations for the group (Z/"n"Z)×. In other words, the Gaussian periods and Gauss sums are each other's Fourier transforms. The Gaussian periods generally lie in smaller fields, since for example when "n" is a prime "p", the values χ("a") are ("p" − 1)-th roots of unity. On the other hand, Gauss sums have nicer algebraic properties.


Continuous q-Laguerre polynomials

In mathematics, the continuous "q"-Laguerre polynomials are a family of basic hypergeometric orthogonal polynomials in the basic Askey scheme. give a detailed list of their properties.
Definition.
The polynomials are given in terms of basic hypergeometric functions and the q-Pochhammer symbol by 。
formula_1formula_2


8525 Nielsabel


Monoid ring

In abstract algebra, a monoid ring is a ring constructed from a ring and a monoid, just as a group ring is constructed from a ring and a group.
Definition.
Let "R" be a ring and let "G" be a monoid. The monoid ring or monoid algebra of "G" over "R", denoted "R"["G"] or "RG", is the set of formal sums formula_1,
where formula_2 for each formula_3 and "r""g" = 0 for all but finitely many "g", equipped with coefficient-wise addition, and the multiplication in which the elements of "R" commute with the elements of "G". More formally, "R"["G"] is the set of functions such that } is finite, equipped with addition of functions, and with multiplication defined by
If "G" is a group, then "R"["G"] is also called the group ring of "G" over "R".
Universal property.
Given "R" and "G", there is a ring homomorphism sending each "r" to "r"1 (where 1 is the identity element of "G"),
and a monoid homomorphism (where the latter is viewed as a monoid under multiplication) sending each "g" to 1"g" (where 1 is the multiplicative identity of "R").
We have that α("r") commutes with β("g") for all "r" in "R" and "g" in "G".
The universal property of the monoid ring states that given a ring "S", a ring homomorphism , and a monoid homomorphism to the multiplicative monoid of "S",
such that α'("r") commutes with β'("g") for all "r" in "R" and "g" in "G", there is a unique ring homomorphism such that composing α and β with γ produces α' and β
Augmentation.
The augmentation is the ring homomorphism defined by
The kernel of "η" is called the augmentation ideal. It is a free "R"-module with basis consisting of 1 – "g" for all "g" in "G" not equal to 1.
Examples.
Given a ring "R" and the (additive) monoid of natural numbers N (or {"x""n"} viewed multiplicatively), we obtain the ring "R"[{"x""n"}] =: "R"["x"] of polynomials over "R".
The monoid N"n" (with the addition) gives the polynomial ring with "n" variables: "R"[N"n"] =: "R"["X"1, ..., "X""n"].
Generalization.
If "G" is a semigroup, the same construction yields a semigroup ring "R"["G"].


Sparse approximation

Sparse approximation (also known as sparse representation) theory deals with sparse solutions for systems of linear equations. Techniques for finding these solutions and exploiting them in applications have found wide use in image processing, signal processing, machine learning, medical imaging, and more.
Sparse decomposition.
Noiseless observations.
Consider a linear system of equations formula_1, where formula_2 is an underdetermined formula_3 matrix formula_4 and formula_5. The matrix formula_2 (typically assumed to be full-rank) is referred to as the dictionary, and formula_7 is a signal of interest. The core sparse representation problem is defined as the quest for the sparsest possible representation formula_8 satisfying formula_1. Due to the underdetermined nature of formula_2, this linear system admits in general infinitely many possible solutions, and among these we seek the one with the fewest non-zeros. Put formally, we solve
where formula_12 is the formula_13 pseudo-norm, which counts the number of non-zero components of formula_8. This problem is known to be NP-hard with a reduction to NP-complete subset selection problems in combinatorial optimization.
Sparsity of formula_8 implies that only a few (formula_16) components in it are non-zero. The underlying motivation for such a sparse decomposition is the desire to provide the simplest possible explanation of formula_7 as a linear combination of as few as possible columns from formula_2, also referred to as atoms. As such, the signal formula_7 can be viewed as a molecule composed of a few fundamental elements taken from formula_2.
While the above posed problem is indeed NP-Hard, its solution can often be found using approximation algorithms. One such option is a convex relaxation of the problem, obtained by using the formula_21-norm instead of formula_13, where formula_23 simply sums the absolute values of the entries in formula_8. This is known as the basis pursuit (BP) algorithm, which can be handled using any linear programming solver. An alternative approximation method is a greedy technique, such as the matching pursuit (MP), which finds the location of the non-zeros one at a time.
Surprisingly, under mild conditions on formula_2 (using the spark (mathematics), the mutual coherence or the restricted isometry property) and the level of sparsity in the solution, formula_26, the sparse representation problem can be shown to have a unique solution, and BP and MP are guaranteed to find it perfectly.
Noisy observations.
Often the observed signal formula_7 is noisy. By relaxing the equality constraint and imposing an formula_28-norm on the data-fitting term, the sparse decomposition problem becomes
or put in a Lagrangian form,
where formula_31 is replacing the formula_32.
Just as in the noiseless case, these two problems are NP-Hard in general, but can be approximated using pursuit algorithms. More specifically, changing the formula_13 to an formula_21-norm, we obtain
which is known as the basis pursuit denoising. Similarly, matching pursuit can be used for approximating the solution of the above problems, finding the locations of the non-zeros one at a time until the error threshold is met. Here as well, theoretical guarantees suggest that BP and MP lead to nearly optimal solutions depending on the properties of formula_2 and the cardinality of the solution formula_26.
Another interesting theoretical result refers to the case in which formula_2 is unitary. Under this assumption, the problems posed above (with either formula_13 or formula_21) admit closed-form solutions in the form of non-linear shrinkage.
Variations.
There are several variations to the basic sparse approximation problem.
Structured sparsity: In the original version of the problem, any of the atoms in the dictionary can be picked. In the structured (block) sparsity model, instead of picking atoms individually, groups of them are to be picked. These groups can be overlapping and of varying size. The objective is to represent formula_7 such that it is sparse while forcing this block-structure.
Collaborative (joint) sparse coding: The original version of the problem is defined for a single signal formula_7. In the collaborative (joint) sparse coding model, a set of signals is available, each believed to emerge from (nearly) the same set of atoms from formula_2. In this case, the pursuit task aims to recover a set of sparse representations that best describe the data while forcing them to share the same (or close-by) support.
Other structures: More broadly, the sparse approximation problem can be cast while forcing a specific desired structure on the pattern of non-zero locations in formula_8. Two cases of interest that have been extensively studied are tree-based structure, and more generally, a Boltzmann distributed support.
Algorithms.
As already mentioned above, there are various approximation (also referred to as pursuit) algorithms that have been developed for addressing the sparse representation problem:
We mention below a few of these main methods.
Applications.
Sparse approximation ideas and algorithms have been extensively used in signal processing, image processing, machine learning, medical imaging, array processing, data mining, and more. In most of these applications, the unknown signal of interest is modeled as a sparse combination of a few atoms from a given dictionary, and this is used as the regularization of the problem. These problems are typically accompanied by a dictionary learning mechanism that aims to fit formula_2 to best match the model to the given data. The use of sparsity-inspired models has led to state-of-the-art results in a wide set of applications. Recent work suggests that there is a tight connection between sparse representation modeling and deep-learning.


Hadamard product (matrices)

In mathematics, the Hadamard product (also known as the element-wise, entrywise or Schur product) is a binary operation that takes two matrices of the same dimensions and produces another matrix of the same dimension as the operands, where each element is the product of elements of the original two matrices. It is to be distinguished from the more common matrix product. It is attributed to, and named after, either French mathematician Jacques Hadamard or German mathematician Issai Schur.
The Hadamard product is associative and distributive. Unlike the matrix product, it is also commutative.
Definition.
For two matrices and of the same dimension , the Hadamard product formula_1 (or formula_2) is a matrix of the same dimension as the operands, with elements given by
For matrices of different dimensions ( and , where or ), the Hadamard product is undefined.
Example.
For example, the Hadamard product for a 3 × 3 matrix with a 3 × 3 matrix is
Schur product theorem.
The Hadamard product of two positive-semidefinite matrices is positive-semidefinite. This is known as the Schur product theorem, after Russian mathematician Issai Schur. For two positive-semidefinite matrices and , it is also known that the determinant of their Hadamard product is greater than or equal to the product of their respective determinants:
In programming languages.
Hadamard multiplication is built into certain programming languages under various names. In MATLAB, GNU Octave, GAUSS and HP Prime, it is known as "array multiplication", or in Julia "broadcast multiplication", with the symbol codice_1. In Fortran, R, APL, J and Wolfram Language (Mathematica), it is done through simple multiplication operator codice_2, whereas the matrix product is done through the function codice_3, codice_4, codice_5, codice_6 and the codice_7 operators, respectively.
In Python with the NumPy numerical library, multiplication of objects as codice_8 produces the Hadamard product, and multiplication as codice_9 produces the matrix product. With the SymPy symbolic library, multiplication of objects as both codice_8 and codice_9 will produce the matrix product, the Hadamard product can be obtained with codice_12.
In C++, the Eigen library provides a codice_13 member function for the class (codice_14), while the Armadillo library uses the operator codice_15 to make compact expressions (codice_16; codice_17 is a matrix product). R package matrixcalc introduces function codice_18 for Hadamard Product of numeric matrices or vectors.
Applications.
The Hadamard product appears in lossy compression algorithms such as JPEG. The decoding step involves an entry-for-entry product, in other words the Hadamard product.
It is also used in the machine learning literature, for example to describe the architecture of recurrent neural networks as GRUs or LSTMs.
Analogous operations.
Other Hadamard operations are also seen in the mathematical literature, namely the "Hadamard root" and "Hadamard power" (which are in effect the same thing because of fractional indices), defined for a matrix such that:
For
and for
The "Hadamard inverse" reads:
A "Hadamard division" is defined as:
The penetrating face product.
According to the definition of V. Slyusar the penetrating face product of the "p"×"g" matrix formula_16 and "n"-dimensional matrix formula_17 ("n" > 1) with "p"×"g" blocks (formula_18) is a matrix of size formula_17 of the form:
Example.
If
then
Main properties.
where formula_25 denotes the face-splitting product of matrices,
Applications.
The penetrating face product is used in the tensor-matrix theory of digital antenna arrays. This operation can also be used in artificial neural network models, specifically convolutional layers.


Emmanuel Ullmo

Emmanuel Ullmo (born 25 June 1965) is a French mathematician, specialised in arithmetic geometry. Since 2013 he has served as director of the Institut des Hautes Études scientifiques.
Biography.
He wrote his thesis under Lucien Szpiro at the University of Paris-Sud in 1993, where he was appointed professor in 2001. He also held temporary positions at IMPA for 18 months, then two years at Princeton University, and six months at Tsinghua University.
He was an editor of the journal "Inventiones mathematicae" between 2007 and 2014.
In 2013, following the retirement of Jean-Pierre Bourguignon, he became the 5th director of the IHÉS.
Awards.
He was an invited speaker at the International Congress of Mathematicians at Beijing in 2002. Between 2003 and 2008 he was a junior fellow at the Institut de France. He received the Elie Cartan Prize of the French Academy of Sciences in 2006 for his work on the proof of the Bogomolov conjecture with Shou-Wu Zhang.


Jean-Louis Loday

Jean-Louis Loday (12 January 1946 – 6 June 2012) was a French mathematician who worked on cyclic homology and who introduced Leibniz algebras (sometimes called Loday algebras) and Zinbiel algebras.
He occasionally used the pseudonym Guillaume William Zinbiel, formed by reversing the last name of Gottfried Wilhelm Leibniz.
Loday studied at Lycée Louis-le-Grand and at École Normale Supérieure in Paris. He completed his Ph.D. at the University of Strasbourg in 1975 under the supervision of Max Karoubi, with a dissertation titled "K-Théorie algébrique et représentations de groupes". He went on to become a senior scientist at CNRS and a member of the Institute for Advanced Mathematical Research (IRMA) at the University of Strasbourg.


Transpose

In linear algebra, the transpose of a matrix is an operator which flips a matrix over its diagonal;
that is, it switches the row and column indices of the matrix by producing another matrix, often denoted by (among other notations).
The transpose of a matrix was introduced in 1858 by the British mathematician Arthur Cayley.
Transpose of a matrix.
Definition.
The transpose of a matrix , denoted by , , , formula_1, , , or , may be constructed by any one of the following methods:
Formally, the -th row, -th column element of is the -th row, -th column element of :
If is an matrix, then is an matrix.
In the case of square matrices, may also denote the th power of the matrix . For avoiding a possible confusion, many authors use left upperscripts, that is, they denote the transpose as . An advantage of this notation is that no parentheses are needed when exponents are involved: as , notation is not ambiguous.
In this article this confusion is avoided by never using the symbol as a variable name.
Matrix definitions involving transposition.
A square matrix whose transpose is equal to itself is called a "symmetric matrix"; that is, is symmetric if
A square matrix whose transpose is equal to its negative is called a "skew-symmetric matrix"; that is, is skew-symmetric if
A square complex matrix whose transpose is equal to the matrix with every entry replaced by its complex conjugate (denoted here with an overline) is called a "Hermitian matrix" (equivalent to the matrix being equal to its conjugate transpose); that is, is Hermitian if
A square complex matrix whose transpose is equal to the negation of its complex conjugate is called a "skew-Hermitian matrix"; that is, is skew-Hermitian if
A square matrix whose transpose is equal to its inverse is called an "orthogonal matrix"; that is, is orthogonal if
A square complex matrix whose transpose is equal to its conjugate inverse is called a "unitary matrix"; that is, is unitary if
Properties.
Let and be matrices and be a scalar.
 \mathbf{b},</math>
which is written as in Einstein summation convention.
Products.
If is an matrix and is its transpose, then the result of matrix multiplication with these two matrices gives two square matrices: is and is . Furthermore, these products are symmetric matrices. Indeed, the matrix product has entries that are the inner product of a row of with a column of . But the columns of are the rows of , so the entry corresponds to the inner product of two rows of . If is the entry of the product, it is obtained from rows and in . The entry is also obtained from these rows, thus , and the product matrix () is symmetric. Similarly, the product is a symmetric matrix.
A quick proof of the symmetry of results from the fact that it is its own transpose:
Implementation of matrix transposition on computers.
On a computer, one can often avoid explicitly transposing a matrix in memory by simply accessing the same data in a different order. For example, software libraries for linear algebra, such as BLAS, typically provide options to specify that certain matrices are to be interpreted in transposed order to avoid the necessity of data movement.
However, there remain a number of circumstances in which it is necessary or desirable to physically reorder a matrix in memory to its transposed ordering. For example, with a matrix stored in row-major order, the rows of the matrix are contiguous in memory and the columns are discontiguous. If repeated operations need to be performed on the columns, for example in a fast Fourier transform algorithm, transposing the matrix in memory (to make the columns contiguous) may improve performance by increasing memory locality.
Ideally, one might hope to transpose a matrix with minimal additional storage. This leads to the problem of transposing an "n" × "m" matrix in-place, with O(1) additional storage or at most storage much less than "mn". For "n" ≠ "m", this involves a complicated permutation of the data elements that is non-trivial to implement in-place. Therefore, efficient in-place matrix transposition has been the subject of numerous research publications in computer science, starting in the late 1950s, and several algorithms have been developed.
Transposes of linear maps and bilinear forms.
Recall that matrices can be placed into a one-to-one correspondence with linear operators.
The transpose of a linear operator can be defined without any need to consider a matrix representation of it.
This leads to a much more general definition of the transpose that can be applied to linear operators that cannot be represented by matrices (e.g. involving many infinite dimensional vector spaces).
Transpose of a linear map.
Let denote the algebraic dual space of an -module .
Let and be -modules.
If is a linear map, then its algebraic adjoint or dual, is the map defined by .
The resulting functional is called the pullback of by .
The following relation characterizes the algebraic adjoint of
where is the natural pairing (i.e. defined by ).
This definition also applies unchanged to left modules and to vector spaces.
The definition of the transpose may be seen to be independent of any bilinear form on the modules, unlike the adjoint (below).
The continuous dual space of a topological vector space (TVS) is denoted by .
If and are TVSs then a linear map is weakly continuous if and only if , in which case we let denote the restriction of to .
The map is called the transpose of .
If the matrix describes a linear map with respect to bases of and , then the matrix describes the transpose of that linear map with respect to the dual bases.
Transpose of a bilinear form.
Every linear map to the dual space defines a bilinear form , with the relation .
By defining the transpose of this bilinear form as the bilinear form defined by the transpose i.e. , we find that .
Here, is the natural homomorphism into the double dual.
Adjoint.
If the vector spaces and have respectively nondegenerate bilinear forms and , a concept known as the adjoint, which is closely related to the transpose, may be defined:
If is a linear map between vector spaces and , we define as the adjoint of if satisfies
These bilinear forms define an isomorphism between and , and between and , resulting in an isomorphism between the transpose and adjoint of .
The matrix of the adjoint of a map is the transposed matrix only if the bases are orthonormal with respect to their bilinear forms.
In this context, many authors use the term transpose to refer to the adjoint as defined here.
The adjoint allows us to consider whether is equal to .
In particular, this allows the orthogonal group over a vector space with a quadratic form to be defined without reference to matrices (nor the components thereof) as the set of all linear maps for which the adjoint equals the inverse.
Over a complex vector space, one often works with sesquilinear forms (conjugate-linear in one argument) instead of bilinear forms.
The Hermitian adjoint of a map between such spaces is defined similarly, and the matrix of the Hermitian adjoint is given by the conjugate transpose matrix if the bases are orthonormal.


Mahler polynomial

In mathematics, the Mahler polynomials "g""n"("x") are polynomials introduced by in his work on the zeros of the incomplete gamma function.
Mahler polynomials are given by the generating function
Mahler polynomials can be given as the Sheffer sequence for the functional inverse of 1+"t"–"e""t" .
The first few examples are


Ross Street

Ross Howard Street (born 29 September 1945, Sydney) is an Australian mathematician specialising in category theory.
Biography.
Street completed his undergraduate and postgraduate study at the University of Sydney, where his dissertation advisor was Max Kelly. He is an emeritus professor of mathematics at Macquarie University, a fellow of the Australian Mathematical Society (1995), and was elected Fellow of the Australian Academy of Science in 1989. He was awarded the Edgeworth David Medal of the Royal Society of New South Wales in 1977, and the Australian Mathematical Society's George Szekeres Medal in 2012.


Quasithin group

In mathematics, a quasithin group is a finite simple group that resembles a group of Lie type of rank at most 2 over a field of characteristic 2. More precisely it is a finite simple group of characteristic 2 type and width 2. Here characteristic 2 type means that its centralizers of involutions resemble those of groups of Lie type over fields of characteristic 2, and the width is roughly the maximal rank of an abelian group of odd order normalizing a non-trivial 2-subgroup of "G". When "G" is a group of Lie type of characteristic 2 type, the width is usually the rank (the dimension of a maximal torus of the algebraic group).
Classification.
The classification of quasithin groups is a crucial part of the classification of finite simple groups. The quasithin groups were classified in a 1221-page paper by . An earlier announcement by of the classification, on the basis of which the classification of finite simple groups was announced as finished in 1983, was premature as the unpublished manuscript of his work was incomplete and contained serious gaps.
According to , the finite simple quasithin groups of even characteristic are given by
If the condition "even characteristic" is relaxed to "even type" in the sense of the revision of the classification by Daniel Gorenstein, Richard Lyons, and Ronald Solomon, then the only extra group that appears is the Janko group J1.


O*-algebra

In mathematics, an O*-algebra is an algebra of possibly unbounded operators defined on a dense subspace of a Hilbert space. The original examples were described by and , who studied some examples of O*-algebras, called Borchers algebras, arising from the Wightman axioms of quantum field theory. and began the systematic study of algebras of unbounded operators.


Algebraic graph theory

Algebraic graph theory is a branch of mathematics in which algebraic methods are applied to problems about graphs. This is in contrast to geometric, combinatoric, or algorithmic approaches. There are three main branches of algebraic graph theory, involving the use of linear algebra, the use of group theory, and the study of graph invariants.
Branches of algebraic graph theory.
Using linear algebra.
The first branch of algebraic graph theory involves the study of graphs in connection with linear algebra. Especially, it studies the spectrum of the adjacency matrix, or the Laplacian matrix of a graph (this part of algebraic graph theory is also called spectral graph theory). For the Petersen graph, for example, the spectrum of the adjacency matrix is (−2, −2, −2, −2, 1, 1, 1, 1, 1, 3). Several theorems relate properties of the spectrum to other graph properties. As a simple example, a connected graph with diameter "D" will have at least "D"+1 distinct values in its spectrum. Aspects of graph spectra have been used in analysing the synchronizability of networks.
Using group theory.
The second branch of algebraic graph theory involves the study of graphs in connection to group theory, particularly automorphism groups and geometric group theory. The focus is placed on various families of graphs based on symmetry (such as symmetric graphs, vertex-transitive graphs, edge-transitive graphs, distance-transitive graphs, distance-regular graphs, and strongly regular graphs), and on the inclusion relationships between these families. Certain of such categories of graphs are sparse enough that lists of graphs can be drawn up. By Frucht's theorem, all groups can be represented as the automorphism group of a connected graph (indeed, of a cubic graph). Another connection with group theory is that, given any group, symmetrical graphs known as Cayley graphs can be generated, and these have properties related to the structure of the group.
This second branch of algebraic graph theory is related to the first, since the symmetry properties of a graph are reflected in its spectrum. In particular, the spectrum of a highly symmetrical graph, such as the Petersen graph, has few distinct values (the Petersen graph has 3, which is the minimum possible, given its diameter). For Cayley graphs, the spectrum can be related directly to the structure of the group, in particular to its irreducible characters.
Studying graph invariants.
Finally, the third branch of algebraic graph theory concerns algebraic properties of invariants of graphs, and especially the chromatic polynomial, the Tutte polynomial and knot invariants. The chromatic polynomial of a graph, for example, counts the number of its proper vertex colorings. For the Petersen graph, this polynomial is formula_1. In particular, this means that the Petersen graph cannot be properly colored with one or two colors, but can be colored in 120 different ways with 3 colors. Much work in this area of algebraic graph theory was motivated by attempts to prove the four color theorem. However, there are still many open problems, such as characterizing graphs which have the same chromatic polynomial, and determining which polynomials are chromatic.


Indefinite orthogonal group

In mathematics, the indefinite orthogonal group, is the Lie group of all linear transformations of an "n"-dimensional real vector space that leave invariant a nondegenerate, symmetric bilinear form of signature , where . The dimension of the group is .
The indefinite special orthogonal group, is the subgroup of consisting of all elements with determinant 1. Unlike in the definite case, is not connected – it has 2 components – and there are two additional finite index subgroups, namely the connected and , which has 2 components – see "" for definition and discussion.
The signature of the form determines the group up to isomorphism; interchanging "p" with "q" amounts to replacing the metric by its negative, and so gives the same group. If either "p" or "q" equals zero, then the group is isomorphic to the ordinary orthogonal group O("n"). We assume in what follows that both "p" and "q" are positive.
The group is defined for vector spaces over the reals. For complex spaces, all groups are isomorphic to the usual orthogonal group , since the transform formula_1 changes the signature of a form. This should not be confused with the indefinite unitary group which preserves a sesquilinear form of signature .
In even dimension , is known as the split orthogonal group.
Examples.
The basic example is the squeeze mappings, which is the group of (the identity component of) linear transforms preserving the unit hyperbola. Concretely, these are the matrices formula_2 and can be interpreted as "hyperbolic rotations," just as the group SO(2) can be interpreted as "circular rotations."
In physics, the Lorentz group is of central importance, being the setting for electromagnetism and special relativity. (Some texts use for the Lorentz group; however, is prevalent in quantum field theory because the geometric properties of the Dirac equation are more natural in .)
Matrix definition.
One can define as a group of matrices, just as for the classical orthogonal group O("n"). Consider the formula_3 diagonal matrix formula_4 given by
Then we may define a symmetric bilinear form formula_6 on formula_7 by the formula
where formula_9 is the standard inner product on formula_7.
We then define formula_11 to be the group of formula_3 matrices that preserve this bilinear form:
More explicitly, formula_11 consists of matrices formula_15 such that
where formula_17 is the transpose of formula_15.
One obtains an isomorphic group (indeed, a conjugate subgroup of ) by replacing "g" with any symmetric matrix with "p" positive eigenvalues and "q" negative ones. Diagonalizing this matrix gives a conjugation of this group with the standard group .
Topology.
Assuming both "p" and "q" are positive, neither of the groups nor are connected, having four and two components respectively.
 is the Klein four-group, with each factor being whether an element preserves or reverses the respective orientations on the "p" and "q" dimensional subspaces on which the form is definite; note that reversing orientation on only one of these subspaces reverses orientation on the whole space. The special orthogonal group has components }, each of which either preserves both orientations or reverses both orientations, in either case preserving the overall orientation.
The identity component of is often denoted and can be identified with the set of elements in that preserve both orientations. This notation is related to the notation for the orthochronous Lorentz group, where the + refers to preserving the orientation on the first (temporal) dimension.
The group is also not compact, but contains the compact subgroups O("p") and O("q") acting on the subspaces on which the form is definite. In fact, is a maximal compact subgroup of , while is a maximal compact subgroup of .
Likewise, is a maximal compact subgroup of .
Thus, the spaces are homotopy equivalent to products of (special) orthogonal groups, from which algebro-topological invariants can be computed. (See Maximal compact subgroup.)
In particular, the fundamental group of is the product of the fundamental groups of the components, , and is given by:
Split orthogonal group.
In even dimensions, the middle group is known as the split orthogonal group, and is of particular interest, as it occurs as the group of T-duality transformations in string theory, for example. It is the split Lie group corresponding to the complex Lie algebra so2"n" (the Lie group of the split real form of the Lie algebra); more precisely, the identity component is the split Lie group, as non-identity components cannot be reconstructed from the Lie algebra. In this sense it is opposite to the definite orthogonal group , which is the "compact" real form of the complex Lie algebra.
The case corresponds to the multiplicative group of the split-complex numbers.
In terms of being a group of Lie type – i.e., construction of an algebraic group from a Lie algebra – split orthogonal groups are Chevalley groups, while the non-split orthogonal groups require a slightly more complicated construction, and are Steinberg groups.
Split orthogonal groups are used to construct the generalized flag variety over non-algebraically closed fields.


Biregular


Z-matrix (mathematics)

In mathematics, the class of "Z"-matrices are those matrices whose off-diagonal entries are less than or equal to zero; that is, the matrices of the form:
Note that this definition coincides precisely with that of a negated Metzler matrix or quasipositive matrix, thus the term "quasinegative" matrix appears from time to time in the literature, though this is rare and usually only in contexts where references to quasipositive matrices are made.
The Jacobian of a competitive dynamical system is a "Z"-matrix by definition. Likewise, if the Jacobian of a cooperative dynamical system is "J", then (−"J") is a "Z"-matrix.
Related classes are "L"-matrices, "M"-matrices, "P"-matrices, "Hurwitz" matrices and "Metzler" matrices. "L"-matrices have the additional property that all diagonal entries are greater than zero. M-matrices have several equivalent definitions, one of which is as follows: a "Z"-matrix is an "M"-matrix if it is nonsingular and its inverse is nonnegative. All matrices that are both "Z"-matrices and "P"-matrices are nonsingular "M"-matrices.
In the context of quantum complexity theory, these are referred to as "stoquastic operators".


Transposition (mathematics)


Starred transform

In applied mathematics, the starred transform, or star transform, is a discrete-time variation of the Laplace transform, so-named because of the asterisk or "star" in the customary notation of the sampled signals.
The transform is an operator of a continuous-time function formula_1, which is transformed to a function in the following manner:
where is a Dirac comb function, with period of time T.
The starred transform is a convenient mathematical abstraction that represents the Laplace transform of an "impulse sampled" function , which is the output of an "ideal sampler", whose input is a continuous function, formula_1.
The starred transform is similar to the Z transform, with a simple change of variables, where the starred transform is explicitly declared in terms of the sampling period (T), while the Z transform is performed on a discrete signal and is independent of the sampling period. This makes the starred transform a de-normalized version of the one-sided Z-transform, as it restores the dependence on sampling parameter "T".
Relation to Laplace transform.
Since , where:
Then per the convolution theorem, the starred transform is equivalent to the complex convolution of and </math>}}, hence:
This line integration is equivalent to integration in the positive sense along a closed contour formed by such a line and an infinite semicircle that encloses the poles of X(s) in the left half-plane of "p". The result of such an integration (per the residue theorem) would be:
Alternatively, the aforementioned line integration is equivalent to integration in the negative sense along a closed contour formed by such a line and an infinite semicircle that encloses the infinite poles of </math>}} in the right half-plane of "p". The result of such an integration would be:
Relation to Z transform.
Given a Z-transform, "X"("z"), the corresponding starred transform is a simple substitution:
This substitution restores the dependence on "T".
It's interchangeable,
Properties of the starred transform.
Property 1:  formula_11 is periodic in formula_12 with period formula_13
Property 2:  If has a pole at formula_15, then must have poles at formula_16, where formula_17


Amoeba (mathematics)

In complex analysis, a branch of mathematics, an amoeba is a set associated with a polynomial in one or more complex variables. Amoebas have applications in algebraic geometry, especially tropical geometry.
Definition.
Consider the function
defined on the set of all "n"-tuples formula_2 of non-zero complex numbers with values in the Euclidean space formula_3 given by the formula
Here, log denotes the natural logarithm. If "p"("z") is a polynomial in formula_5 complex variables, its amoeba formula_6 is defined as the image of the set of zeros of "p" under Log, so
Amoebas were introduced in 1994 in a book by Gelfand, Kapranov, and Zelevinsky.
Ronkin function.
A useful tool in studying amoebas is the Ronkin function. For "p"("z"), a polynomial in "n" complex variables, one defines the Ronkin function
by the formula
where formula_11 denotes formula_12 Equivalently, formula_13 is given by the integral
where
The Ronkin function is convex and affine on each connected component of the complement of the amoeba of formula_16.
As an example, the Ronkin function of a monomial
with formula_18 is


Hypercube graph

 | properties = Symmetric
Distance regular
Unit distance
Hamiltonian
Bipartite
 | notation =
In graph theory, the hypercube graph is the graph formed from the vertices and edges of an -dimensional hypercube. For instance, the cubical graph is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube.
 has vertices, edges, and is a regular graph with edges touching each vertex.
The hypercube graph may also be constructed by creating a vertex for each subset of an -element set, with two vertices adjacent when their subsets differ in a single element, or by creating a vertex for each -digit binary number, with two vertices adjacent when their binary representations differ in a single digit. It is the -fold Cartesian product of the two-vertex complete graph, and may be decomposed into two copies of connected to each other by a perfect matching.
Hypercube graphs should not be confused with cubic graphs, which are graphs that have exactly three edges touching each vertex. The only hypercube graph that is a cubic graph is the cubical graph .
Construction.
The hypercube graph may be constructed from the family of subsets of a set with elements, by making a vertex for each possible subset and joining two vertices by an edge whenever the corresponding subsets differ in a single element. Equivalently, it may be constructed using vertices labeled with -bit binary numbers and connecting two vertices by an edge whenever the Hamming distance of their labels is one. These two constructions are closely related: a binary number may be interpreted as a set (the set of positions where it has a digit), and two such sets differ in a single element whenever the corresponding two binary numbers have Hamming distance one.
Alternatively, may be constructed from the disjoint union of two hypercubes , by adding an edge from each vertex in one copy of to the corresponding vertex in the other copy, as shown in the figure. The joining edges form a perfect matching.
Another construction of is the Cartesian product of two-vertex complete graphs . More generally the Cartesian product of copies of a complete graph is called a Hamming graph; the hypercube graphs are examples of Hamming graphs.
Examples.
The graph consists of a single vertex, while is the complete graph on two vertices and is a cycle of length .
The graph is the 1-skeleton of a cube, a cubical graph, a planar graph with eight vertices and twelve edges.
The graph is the Levi graph of the Möbius configuration. It is also the knight's graph for a toroidal formula_1 chessboard.
Properties.
Bipartiteness.
Every hypercube graph is bipartite: it can be colored with only two colors. The two colors of this coloring may be found from the subset construction of hypercube graphs, by giving one color to the subsets that have an even number of elements and the other color to the subsets with an odd number of elements.
Hamiltonicity.
Every hypercube with has a Hamiltonian cycle, a cycle that visits each vertex exactly once. Additionally, a Hamiltonian path exists between two vertices and if and only if they have different colors in a -coloring of the graph. Both facts are easy to prove using the principle of induction on the dimension of the hypercube, and the construction of the hypercube graph by joining two smaller hypercubes with a matching.
Hamiltonicity of the hypercube is tightly related to the theory of Gray codes. More precisely there is a bijective correspondence between the set of -bit cyclic Gray codes and the set of Hamiltonian cycles in the hypercube . An analogous property holds for acyclic "n"-bit Gray codes and Hamiltonian paths.
A lesser known fact is that every perfect matching in the hypercube extends to a Hamiltonian cycle. The question whether every matching extends to a Hamiltonian cycle remains an open problem.
Other properties.
The hypercube graph (for ) :
The family for all is a Lévy family of graphs
Problems.
The problem of finding the longest path or cycle that is an induced subgraph of a given hypercube graph is known as the snake-in-the-box problem.
Szymanski's conjecture concerns the suitability of a hypercube as a network topology for communications. It states that, no matter how one chooses a permutation connecting each hypercube vertex to another vertex with which it should be connected, there is always a way to connect these pairs of vertices by paths that do not share any directed edge.