User:Richard Pinch/sandbox-WP2

Average order of an arithmetic function

Some simpler or better-understood function which takes the same values "on average" as an arithmetic function.

Let f be a function on the natural numbers. We say that f has average order g if

\[ \sum_{n \le x} f(n) \sim \sum_{n \le x} g(n) \]

as x tends to infinity.

It is conventional to assume that the approximating function g is continuous and monotone.

Examples

• The average order of $d(n)$, the number of divisors of $n$, is $\log n$;
• The average order of $\sigma(n)$, the sum of divisors of $n$, is $ \frac{\pi^2}{6} n$;
• The average order of $\phi(n)$, Euler's totient function of $n$, is $ \frac{6}{\pi^2} n$;
• The average order of $r(n)$, the number of ways of expressing $n$ as a sum of two squares, is $\pi$;
• The Prime Number Theorem is equivalent to the statement that the von Mangoldt function $\Lambda(n)$ has average order 1.

See also

• Divisor function
• Normal order of an arithmetic function

References

• G.H. Hardy; E.M. Wright (2008). An Introduction to the Theory of Numbers (6th ed.). Oxford University Press. ISBN 0-19-921986-5
• Gérald Tenenbaum (1995). Introduction to Analytic and Probabilistic Number Theory. Cambridge studies in advanced mathematics 46. Cambridge University Press. ISBN 0-521-41261-7

Gowers norm

For the function field norm, see uniform norm; for uniformity in topology, see uniform space.

In mathematics, in the field of additive combinatorics, a Gowers norm or uniformity norm is a class of norm on functions on a finite group or group-like object which are used in the study of arithmetic progressions in the group. They are named after Timothy Gowers who introduced them in his work on Szemerédi's theorem.

Let f be a complex-valued function on a group G and let J denote complex conjugation. The Gowers d-norm is

\[ \Vert f \Vert_{U^d(g)} = \mathbf{E}_{x,h_1,\ldots,h_d \in G} \prod_{\omega_1,\ldots,\omega_d \in \{0,1\}} J^{\omega_1+\cdots+\omega_d} f\left({x + h_1\omega_1 + \cdots + h_d\omega_d}\right) \ . \]

The inverse conjecture for these norms is the statement that if f has L-infinity norm (uniform norm in the usual sense) equal to 1 then the Gowers s-norm is bounded above by 1, with equality if and only if f is of the form exp(2πi g) with g a polynomial of degree at most s. This can be interpreted as saying that the Gowers norm is controlled by polynomial phases.

The inverse conjecture holds for vector spaces over a finite field. However, for cyclic groups Z/N this is not so, and the class of polynomial phases has to be extended to control the norm.

References

• Tao, Terence; Higher order Fourier analysis, ser. Graduate Studies in Mathematics 142 (2012), American Mathematical Society, Zbl pre06110460URL: http://terrytao.wordpress.com/books/higher-order-fourier-analysis/] ISBN: 978-0-8218-8986-2

Ruelle zeta function

A zeta function associated with a dynamical system.

Let f be a function defined on a manifold M, such that the set of fixed points Fix(f ⁿ) is finite for all n > 1. Further let φ be a function on M with values in d × d complex matrices. The zeta function of the first kind is

\[ \zeta(z) = \exp\left({ \sum_{m\ge1} \frac{z^m}{m} \sum_{x\in\mathrm{Fix}(f^m)} \mathrm{Tr} \left({ \prod_{k=0}^{m-1} \phi(f^k(x)) }\right) }\right) \]

In the special case d = 1, φ = 1, we have

\[ \zeta(z) = \exp\left({ \sum_{m\ge1} \frac{z^m}{m} \left|{\mathrm{Fix}(f^m)}\right|}\right) \]

which is the Artin–Mazur zeta function.

The Ihara zeta function is an example of a Ruelle zeta function.

References

• Lapidus, Michel L.; van Frankenhuijsen, Machiel; Fractal geometry, complex dimensions and zeta functions. Geometry and spectra of fractal strings, ser. Springer Monographs in Mathematics (2006), Springer-Verlag, Zbl 1119.28005 ISBN: 0-387-33285-5
• Terras, Audrey; Zeta Functions of Graphs: A Stroll through the Garden, ser. Cambridge Studies in Advanced Mathematics 128 (2010), Cambridge University Press, Zbl 1206.05003 ISBN: 0-521-11367-9

Sesquipower

A sesquipower or Zimin word is a string over an alphabet with identical prefix and suffix. Sesquipowers are unavoidable patterns, in the sense that all sufficiently long strings contain one.

Formally, let A be an alphabet and A^∗ be the free monoid of finite strings over A. Every non-empty word w in A⁺ is a sesquipower of order 1. If u is a sequipower of order n then any word w = uvu is a sesquipower of order n + 1. The degree of a non-empty word w is the largest integer d such that w is a sesquipower of order d.

A bi-ideal sequence is a sequence of words f_i where f₁ is in A⁺ and

\[f_{i+1} = f_i g_i f_i \ \]

for some g_i in A^∗ and i ≥ 1. The degree of a word w is thus the length of the longest bi-ideal sequence ending in w.

For a finite alphabet A on k letters, there is an integer M depending on k and n, such that any word of length M has a factor which is a sesquipower of order at least n. We express this by saying that the sesquipowers are unavoidable patterns.

Given an infinite bi-ideal sequence, we note that each f_i is a prefix of f_i+1 and so the f_i converge to an infinite sequence

\[ f = f_1 g_1 f_2 g_2 \cdots \ \]

We define an infinite word to be a sesquipower if is the limit of an infinite bi-ideal sequence. An infinite word is a sesquipower if and only if it is a recurrent word, that is, every factor occurs infinitely often.

Fix a finite alphabet A and assume a total order on the letters. For given integers p and n, every sufficiently long word in A^∗ has either a factor which is a p-power or a factor which is an n-sesquipower; in the latter case the factor has an n-factorisation into Lyndon words.

References

• Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V.; Combinatorics on words. Christoffel words and repetitions in words, ser. CRM Monograph Series 27 (2009), American Mathematical Society, Zbl 1161.68043URL: http://www.ams.org/bookpages/crmm-27] ISBN: 978-0-8218-4480-9
• Lothaire, M.; Algebraic combinatorics on words, ser. Encyclopedia of Mathematics and Its Applications 90 (2011), Cambridge University Press, Zbl 1221.68183 ISBN: 978-0-521-18071-9
• Pytheas Fogg, N.; Substitutions in dynamics, arithmetics and combinatorics, ser. Lecture Notes in Mathematics 1794 (2002), Springer-Verlag, Zbl 1014.11015 ISBN: 3-540-44141-7

Spectrum of a sentence

The set of natural numbers that occur as the size of a finite model in which the sentence is true.

Definition

Let $\psi$ be a sentence in first-order logic. The spectrum of $\psi$ is the set of natural numbers $n$ such that there is a finite model for $\psi$ with $n$ elements.

If the vocabulary for $\psi$ consists of relational symbols, then $\psi$ can be regarded as a sentence in existential second-order logic quantified over the relations, over the empty vocabulary. A generalised spectrum is the set of models of a general ESOL sentence.

Properties

Fagin's theorem is a result in descriptive complexity theory that states that the set of all properties expressible in existential second-order logic is precisely the complexity class NP. It is remarkable since it is a characterization of the class NP that does not invoke a model of computation such as a Turing machine. The theorem was proven by Ronald Fagin in 1974 (strictly, in 1973 in his doctoral thesis).

As a corollary we have a result of Jones and Selman, that a set is a spectrum if and only if it is in the complexity class NEXPTIME.

See also

• Spectrum of a theory

References

• Fagin, Ronald; Complexity of Computation, "Generalized First-Order Spectra and Polynomial-Time Recognizable Sets", ser. Proc. Syp. App. Math. SIAM-AMS Proceedings 7 (1974), pp. 27–41, Zbl 0303.68035 URL: www.almaden.ibm.com/cs/people/fagin/genspec.pdf
• Grädel, Erich; Kolaitis, Phokion G.; Libkin, Leonid; Maarten, Marx; Spencer, Joel; Vardi, Moshe Y.; Finite model theory and its applications, ser. Texts in Theoretical Computer Science. An EATCS Series (2007), Springer-Verlag, Zbl 1133.03001 ISBN 978-3-540-00428-8
• Immerman, Neil; Descriptive Complexity, ser. Graduate Texts in Computer Science (1999), pp. 113–119, Springer-Verlag, Zbl 0918.68031 ISBN 0-387-98600-6
• Jones, Neil D.; Selman, Alan L.; Turing machines and the spectra of first-order formulas, J. Symb. Log., 39 (1974), pp. 139-150, Zbl 0288.02021, DOI: 10.2307/2272354

Spinor genus

A classification of quadratic forms and lattices over the ring of integers, introduced by Martin Eichler. It refines the genus but may be coarser than proper equivalence

We define two Z-lattices L and M in a quadratic space V over Q to be spinor equivalent if there exists a transformation g in the proper orthogonal group O⁺(V) and for every prime p there exists a local transformation f_p of V_p of spinor norm 1 such that M = g f_pL_p.

A spinor genus is an equivalence class for this equivalence relation. Properly equivalent lattices are in the same spinor genus, and lattices in the same spinor genus are in the same genus. The number of spinor genera in a genus is a power of two, and can be determined effectively.

An important result is that for indefinite forms of dimension at least three, each spinor genus contains exactly one proper equivalence class.

References

• Cassels, J. W. S.; Rational Quadratic Forms, ser. London Mathematical Society Monographs 13 (1978), Academic Press, Zbl 0395.10029 ISBN: 0-12-163260-1
• Conway, J. H.; Sloane, N. J. A.; Sphere packings, lattices and groups, ser. Grundlehren der Mathematischen Wissenschaften 290 , Springer-Verlag, Zbl 0915.52003 ISBN: 0-387-98585-9

Universal invariant

$u$-invariant

A numerical invariant of a field describing the structure of quadratic forms over the field.

The universal invariant $u(F)$ of a field $F$ is the largest dimension of an anisotropic quadratic space over $F$, or $\infty$ if this does not exist. Since formally real fields have anisotropic quadratic forms (sums of squares) in every dimension, the invariant is only of interest for other fields. An equivalent formulation is that $u(F)$ is the smallest number such that every form of dimension greater than $u$' is isotropic, or that every form of dimension at least $u$ is a universal quadratic form.

Examples

• For the field of complex numbers, $u(\mathbb{C}) = 1$.
• A quadratically closed field has $u = 1$.
• The function field of an algebraic curve over an algebraically closed field has $u \le 2$; this follows from Tsen's theorem that such a field is quasi-algebraically closed.
• If $F$ is a nonreal global or local field, or more generally a linked field, then $u(F) = 1,2,4 \,\text{or}\, 8$.

Properties

• If $F$ is not formally real then $u(F)$ is at most $q(F) = \left|{F^\star / F^{\star2}}\right|$, the index of the squares in the multiplicative group of $F$.
• Every even integer occurs as the value of $u(F)$ for some $F$.
• $u(F)$ cannot take the values 3, 5, or 7. A field exists with u = 9.

The general $u$-invariant

Since the $u$invariant is of little interest in the case of formally real fields, we define a general $u$-invariant to be the maximum dimension of an anisotropic form in the torsion subgroup of the Witt ring of $F$, or $\infty$ if this does exist. For non-formally real fields, the Witt ring is torsion, so this agrees with the previous definition. For a formally real field, the general $u$-invariant is either even or $\infty$.

Properties

• $u(F) \le 1$ if and only if $F$ is a Pythagorean field.

References

• Lam, Tsit-Yuen; Introduction to Quadratic Forms over Fields, ser. Graduate Studies in Mathematics 67 (2005), American Mathematical Society, Zbl 1068.11023 ISBN: 0-8218-1095-2
• Rajwade, A. R.; Squares, ser. London Mathematical Society Lecture Note Series 171 (1993), Cambridge University Press, Zbl 0785.11022 ISBN: 0-521-42668-5

Zimmert set

A set of positive integers associated with the structure of quotients of hyperbolic three-space by a Bianchi group.

Fix an integer $d$ and let $D$ be the discriminant of the imaginary quadratic field $\mathbb{Q}(\sqrt{-d}$. The Zimmert set $Z(d)$ is the set of positive integers $n$ such that $4n^2 < -D-3$ and $n \ne 2$; $D$ is a quadratic non-residue of all odd primes in $d$; $n$ is odd if $D$ is not congruent to 5 modulo 8. The cardinality of $Z(d)$ may be denoted by $z(d)$.

For all but a finite number of $d$ we have $z(d)>1$: indeed this is true for all $d > 10^{476}$.

Let $\Gamma_d$ Bianchi group $PSL(2,O_d)$, where $O_d$ is the ring of integers of $\mathbb{Q}(\sqrt{-d}$. As a subgroup of $PSL(2,\mathbb{C})$, there is an action of $\Gamma_d$ on hyperbolic 3-space $H^3$, with a fundamental domain. It is a theorem that there are only finitely many values of $d$ for which$\Gamma_d$ can contain an arithmetic subgroup $G$ for which the quotient $H^3/G$ is a link complement. Zimmert sets are used to obtain results in this direction: $z(d)$ is a lower bound for the rank of the largest free quotient of $\Gamma_d$ and so the result above implies that almost all Bianchi groups have non-cyclic free quotients.

References

• Maclachlan, Colin; Reid, Alan W.; The Arithmetic of Hyperbolic 3-Manifolds, ser. Graduate Texts in Mathematics 219 (2003), Springer-Verlag, Zbl 1025.57001 ISBN: 0-387-98386-4