Landau's function

Last updated July 18, 2024

In mathematics, Landau's functiong(n), named after Edmund Landau, is defined for every natural number n to be the largest order of an element of the symmetric group S_n. Equivalently, g(n) is the largest least common multiple (lcm) of any partition of n, or the maximum number of times a permutation of n elements can be recursively applied to itself before it returns to its starting sequence.

For instance, 5 = 2 + 3 and lcm(2,3) = 6. No other partition of 5 yields a bigger lcm, so g(5) = 6. An element of order 6 in the group S₅ can be written in cycle notation as (1 2) (3 4 5). Note that the same argument applies to the number 6, that is, g(6) = 6. There are arbitrarily long sequences of consecutive numbers n, n + 1, ..., n + m on which the function g is constant.^[1]

The integer sequence g(0) = 1, g(1) = 1, g(2) = 2, g(3) = 3, g(4) = 4, g(5) = 6, g(6) = 6, g(7) = 12, g(8) = 15, ... (sequence A000793 in the OEIS ) is named after Edmund Landau, who proved in 1902^[2] that

\lim _{n\to \infty }{\frac {\ln(g(n))}{\sqrt {n\ln(n)}}}=1

(where ln denotes the natural logarithm). Equivalently (using little-o notation), $g(n)=e^{(1+o(1)){\sqrt {n\ln n}}}$ .

More precisely,^[3]

\ln g(n)={\sqrt {n\ln n}}\left(1+{\frac {\ln \ln n-1}{2\ln n}}-{\frac {(\ln \ln n)^{2}-6\ln \ln n+9}{8(\ln n)^{2}}}+O\left(\left({\frac {\ln \ln n}{\ln n}}\right)^{3}\right)\right).

If $\pi (x)-\operatorname {Li} (x)=O(R(x))$ , where $\pi$ denotes the prime counting function, $\operatorname {Li}$ the logarithmic integral function with inverse $\operatorname {Li} ^{-1}$ , and we may take $R(x)=x\exp {\bigl (}-c(\ln x)^{3/5}(\ln \ln x)^{-1/5}{\bigr )}$ for some constant c > 0 by Ford,^[4] then^[3]

\ln g(n)={\sqrt {\operatorname {Li} ^{-1}(n)}}+O{\bigl (}R({\sqrt {n\ln n}})\ln n{\bigr )}.

The statement that

\ln g(n)<{\sqrt {\mathrm {Li} ^{-1}(n)}}

for all sufficiently large n is equivalent to the Riemann hypothesis.

It can be shown that

g(n)\leq e^{n/e}

with the only equality between the functions at n = 0, and indeed

g(n)\leq \exp \left(1.05314{\sqrt {n\ln n}}\right).

^[5]

Notes

↑ Nicolas, Jean-Louis (1968), "Sur l'ordre maximum d'un élément dans le groupe S_n des permutations", Acta Arithmetica (in French), 14: 315–332
↑ Landau, pp. 92–103
1 2 Massias, J. P.; Nicholas, J. L.; Robin, G. (1988), "Évaluation asymptotique de l'ordre maximum d'un élément du groupe symétrique", Acta Arithmetica (in French), 50: 221–242
↑ Kevin Ford (November 2002). "Vinogradov's Integral and Bounds for the Riemann Zeta Function" (PDF). Proc. London Math. Soc. 85 (3): 565–633. arXiv: 1910.08209 . doi:10.1112/S0024611502013655. S2CID 121144007.
↑ Jean-Pierre Massias, Majoration explicite de l'ordre maximum d'un élément du groupe symétrique, Ann. Fac. Sci. Toulouse Math. (5) 6 (1984), no. 3-4, pp. 269–281 (1985).

Related Research Articles

In complex analysis, an entire function, also called an integral function, is a complex-valued function that is holomorphic on the whole complex plane. Typical examples of entire functions are polynomials and the exponential function, and any finite sums, products and compositions of these, such as the trigonometric functions sine and cosine and their hyperbolic counterparts sinh and cosh, as well as derivatives and integrals of entire functions such as the error function. If an entire function $has a root at, then, taking the limit value at, is an entire function. On the other hand, the natural logarithm, the reciprocal function, and the square root are all not entire functions, nor can they be continued analytically to an entire function.$

The natural logarithm of a number is its logarithm to the base of the mathematical constant $e$ , which is an irrational and transcendental number approximately equal to $2.718 281828459$ . The natural logarithm of $x$ is generally written as $ln x$ , $log e x$ , or sometimes, if the base $e$ is implicit, simply $log x$ . Parentheses are sometimes added for clarity, giving $ln(x)$ , $log e (x)$ , or $log(x)$ . This is done particularly when the argument to the logarithm is not a single symbol, so as to prevent ambiguity.

In probability theory and statistics, the exponential distribution or negative exponential distribution is the probability distribution of the distance between events in a Poisson point process, i.e., a process in which events occur continuously and independently at a constant average rate; the distance parameter could be any meaningful mono-dimensional measure of the process, such as time between production errors, or length along a roll of fabric in the weaving manufacturing process. It is a particular case of the gamma distribution. It is the continuous analogue of the geometric distribution, and it has the key property of being memoryless. In addition to being used for the analysis of Poisson point processes it is found in various other contexts.

In mathematics, the logarithmic integral function or integral logarithm li(x) is a special function. It is relevant in problems of physics and has number theoretic significance. In particular, according to the prime number theorem, it is a very good approximation to the prime-counting function, which is defined as the number of prime numbers less than or equal to a given value $.$

<span class="mw-page-title-main">Log-normal distribution</span> Probability distribution

In probability theory, a log-normal (or lognormal) distribution is a continuous probability distribution of a random variable whose logarithm is normally distributed. Thus, if the random variable $X$ is log-normally distributed, then $Y = ln(X)$ has a normal distribution. Equivalently, if $Y$ has a normal distribution, then the exponential function of $Y$ , $X = exp(Y)$ , has a log-normal distribution. A random variable that is log-normally distributed takes only positive real values. It is a convenient and useful model for measurements in the natural sciences, engineering, as well as medicine, economics and other fields. It can be applied to diverse quantities such as energies, concentrations, lengths, prices of financial instruments, and other metrics, while acknowledging the inherent uncertainty in all measurements.

In mathematics, the error function, often denoted by $erf$ , is a function defined as:

Integration is the basic operation in integral calculus. While differentiation has straightforward rules by which the derivative of a complicated function can be found by differentiating its simpler component functions, integration does not, so tables of known integrals are often useful. This page lists some of the most common antiderivatives.

In mathematics, a Gaussian function, often simply referred to as a Gaussian, is a function of the base form $and with parametric extension for arbitrary real constants a, b and non-zero c . It is named after the mathematician Carl Friedrich Gauss. The graph of a Gaussian is a characteristic symmetric "bell curve" shape. The parameter a is the height of the curve's peak, b is the position of the center of the peak, and c controls the width of the "bell".$

<span class="mw-page-title-main">Prime-counting function</span> Function representing the number of primes less than or equal to a given number

In mathematics, the prime-counting function is the function counting the number of prime numbers less than or equal to some real number $x$ . It is denoted by $π (x)$ (unrelated to the number $π$ ).

In mathematics, theta functions are special functions of several complex variables. They show up in many topics, including Abelian varieties, moduli spaces, quadratic forms, and solitons. As Grassmann algebras, they appear in quantum field theory.

<span class="mw-page-title-main">Tetration</span> Arithmetic operation

In mathematics, tetration is an operation based on iterated, or repeated, exponentiation. There is no standard notation for tetration, though Knuth's up arrow notation $and the left-exponent x b are common.$

In mathematics, the exponential integral Ei is a special function on the complex plane.

In statistics, the Fisher transformation of a Pearson correlation coefficient is its inverse hyperbolic tangent (artanh). When the sample correlation coefficient r is near 1 or -1, its distribution is highly skewed, which makes it difficult to estimate confidence intervals and apply tests of significance for the population correlation coefficient ρ. The Fisher transformation solves this problem by yielding a variable whose distribution is approximately normally distributed, with a variance that is stable over different values of r.

In combinatorics, the symbolic method is a technique for counting combinatorial objects. It uses the internal structure of the objects to derive formulas for their generating functions. The method is mostly associated with Philippe Flajolet and is detailed in Part A of his book with Robert Sedgewick, Analytic Combinatorics, while the rest of the book explains how to use complex analysis in order to get asymptotic and probabilistic results on the corresponding generating functions.

In mathematics, specifically the theory of elliptic functions, the nome is a special function that belongs to the non-elementary functions. This function is of great importance in the description of the elliptic functions, especially in the description of the modular identity of the Jacobi theta function, the Hermite elliptic transcendents and the Weber modular functions, that are used for solving equations of higher degrees.

In probability theory and statistics, the generalized extreme value (GEV) distribution is a family of continuous probability distributions developed within extreme value theory to combine the Gumbel, Fréchet and Weibull families also known as type I, II and III extreme value distributions. By the extreme value theorem the GEV distribution is the only possible limit distribution of properly normalized maxima of a sequence of independent and identically distributed random variables. Note that a limit distribution needs to exist, which requires regularity conditions on the tail of the distribution. Despite this, the GEV distribution is often used as an approximation to model the maxima of long (finite) sequences of random variables.

The statistics of random permutations, such as the cycle structure of a random permutation are of fundamental importance in the analysis of algorithms, especially of sorting algorithms, which operate on random permutations. Suppose, for example, that we are using quickselect to select a random element of a random permutation. Quickselect will perform a partial sort on the array, as it partitions the array according to the pivot. Hence a permutation will be less disordered after quickselect has been performed. The amount of disorder that remains may be analysed with generating functions. These generating functions depend in a fundamental way on the generating functions of random permutation statistics. Hence it is of vital importance to compute these generating functions.

Discrepancy of hypergraphs is an area of discrepancy theory.

In probability theory and statistics, the Conway–Maxwell–Poisson distribution is a discrete probability distribution named after Richard W. Conway, William L. Maxwell, and Siméon Denis Poisson that generalizes the Poisson distribution by adding a parameter to model overdispersion and underdispersion. It is a member of the exponential family, has the Poisson distribution and geometric distribution as special cases and the Bernoulli distribution as a limiting case.

In statistics, the Fisher–Tippett–Gnedenko theorem is a general result in extreme value theory regarding asymptotic distribution of extreme order statistics. The maximum of a sample of iid random variables after proper renormalization can only converge in distribution to one of only 3 possible distribution families: the Gumbel distribution, the Fréchet distribution, or the Weibull distribution. Credit for the extreme value theorem and its convergence details are given to Fréchet (1927), Fisher and Tippett (1928), Mises (1936), and Gnedenko (1943).

References

E. Landau, "Über die Maximalordnung der Permutationen gegebenen Grades [On the maximal order of permutations of given degree]", Arch. Math. Phys. Ser. 3, vol. 5, 1903.
W. Miller, "The maximum order of an element of a finite symmetric group", American Mathematical Monthly , vol. 94, 1987, pp. 497–506.
J.-L. Nicolas, "On Landau's function g(n)", in The Mathematics of Paul Erdős, vol. 1, Springer-Verlag, 1997, pp. 228–240.

External links

OEIS sequenceA000793(Landau's function on the natural numbers)

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Nicolas, Jean-Louis (1968), "Sur l'ordre maximum d'un élément dans le groupe S_n des permutations", Acta Arithmetica (in French), 14: 315–332

[2] Landau, pp. 92–103

[mnr88-3] 1 2 Massias, J. P.; Nicholas, J. L.; Robin, G. (1988), "Évaluation asymptotique de l'ordre maximum d'un élément du groupe symétrique", Acta Arithmetica (in French), 50: 221–242

[4] Kevin Ford (November 2002). "Vinogradov's Integral and Bounds for the Riemann Zeta Function" (PDF). Proc. London Math. Soc. 85 (3): 565–633. arXiv: 1910.08209 . doi:10.1112/S0024611502013655. S2CID 121144007.

[5] Jean-Pierre Massias, Majoration explicite de l'ordre maximum d'un élément du groupe symétrique, Ann. Fac. Sci. Toulouse Math. (5) 6 (1984), no. 3-4, pp. 269–281 (1985).

[1]

[2]

[3]

[4]

[5]

Landau's function

Contents

Notes

Related Research Articles

References

External links