Landau's function

Symbol: LandauG —

g(n)

— Landau's function

Landau's function

g(n)

gives the largest order of an element of the symmetric group

{S}_{n}

.

It can be defined arithmetically as the maximum least common multiple of the partitions of

n

, as in 7932c3.

The following table lists conditions such that LandauG(n) is defined in Fungrim.

Domain	Codomain
$n \in \mathbb{Z}_{\ge 0}$	$g(n) \in \mathbb{Z}_{\ge 1}$

Table data:

\left(P, Q\right)

such that

\left(P\right) \;\implies\; \left(Q\right)

References:

https://oeis.org/A000793

Definitions:

Fungrim symbol	Notation	Short description
`LandauG`	$g(n)$	Landau's function
`ZZGreaterEqual`	$\mathbb{Z}_{\ge n}$	Integers greater than or equal to n

Source code for this entry:

Entry(ID("32e430"),
    SymbolDefinition(LandauG, LandauG(n), "Landau's function"),
    Description("Landau's function", LandauG(n), "gives the largest order of an element of the symmetric group", Subscript(S, n), "."),
    Description("It can be defined arithmetically as the maximum least common multiple of the partitions of", n, ", as in", EntryReference("7932c3"), "."),
    Description("The following table lists conditions such that", SourceForm(LandauG(n)), "is defined in Fungrim."),
    Table(TableRelation(Tuple(P, Q), Implies(P, Q)), TableHeadings(Description("Domain"), Description("Codomain")), List(Tuple(Element(n, ZZGreaterEqual(0)), Element(LandauG(n), ZZGreaterEqual(1))))),
    References("https://oeis.org/A000793"))

6af603

g(n) = \text{A000793}\!\left(n\right)

Assumptions:

n \in \mathbb{Z}_{\ge 0}

References:

Sequence A000793 in Sloane's On-Line Encyclopedia of Integer Sequences (OEIS)

TeX:

g(n) = \text{A000793}\!\left(n\right)

n \in \mathbb{Z}_{\ge 0}

Definitions:

Fungrim symbol	Notation	Short description
`LandauG`	$g(n)$	Landau's function
`SloaneA`	$\text{A00000X}\!\left(n\right)$	Sequence X in Sloane's OEIS
`ZZGreaterEqual`	$\mathbb{Z}_{\ge n}$	Integers greater than or equal to n

Source code for this entry:

Entry(ID("6af603"),
    Formula(Equal(LandauG(n), SloaneA("A000793", n))),
    Variables(n),
    Assumptions(Element(n, ZZGreaterEqual(0))))

177218

Table of

g(n)

for

0 \le n \le 100

$n$	$g(n)$
0	1
1	1
2	2
3	3
4	4
5	6
6	6
7	12
8	15
9	20
10	30
11	30
12	60
13	60
14	84
15	105
16	140
17	210
18	210
19	420
20	420
21	420
22	420
23	840
24	840

$n$	$g(n)$
25	1260
26	1260
27	1540
28	2310
29	2520
30	4620
31	4620
32	5460
33	5460
34	9240
35	9240
36	13860
37	13860
38	16380
39	16380
40	27720
41	30030
42	32760
43	60060
44	60060
45	60060
46	60060
47	120120
48	120120
49	180180

$n$	$g(n)$
50	180180
51	180180
52	180180
53	360360
54	360360
55	360360
56	360360
57	471240
58	510510
59	556920
60	1021020
61	1021020
62	1141140
63	1141140
64	2042040
65	2042040
66	3063060
67	3063060
68	3423420
69	3423420
70	6126120
71	6126120
72	6846840
73	6846840
74	6846840

$n$	$g(n)$
75	6846840
76	8953560
77	9699690
78	12252240
79	19399380
80	19399380
81	19399380
82	19399380
83	38798760
84	38798760
85	58198140
86	58198140
87	58198140
88	58198140
89	116396280
90	116396280
91	116396280
92	116396280
93	140900760
94	140900760
95	157477320
96	157477320
97	232792560
98	232792560
99	232792560
100	232792560

Definitions:

Fungrim symbol	Notation	Short description
`LandauG`	$g(n)$	Landau's function

Source code for this entry:

Entry(ID("177218"),
    Description("Table of", LandauG(n), "for", LessEqual(0, n, 100)),
    Table(Var(n), TableValueHeadings(n, LandauG(n)), TableSplit(4), List(Tuple(0, 1), Tuple(1, 1), Tuple(2, 2), Tuple(3, 3), Tuple(4, 4), Tuple(5, 6), Tuple(6, 6), Tuple(7, 12), Tuple(8, 15), Tuple(9, 20), Tuple(10, 30), Tuple(11, 30), Tuple(12, 60), Tuple(13, 60), Tuple(14, 84), Tuple(15, 105), Tuple(16, 140), Tuple(17, 210), Tuple(18, 210), Tuple(19, 420), Tuple(20, 420), Tuple(21, 420), Tuple(22, 420), Tuple(23, 840), Tuple(24, 840), Tuple(25, 1260), Tuple(26, 1260), Tuple(27, 1540), Tuple(28, 2310), Tuple(29, 2520), Tuple(30, 4620), Tuple(31, 4620), Tuple(32, 5460), Tuple(33, 5460), Tuple(34, 9240), Tuple(35, 9240), Tuple(36, 13860), Tuple(37, 13860), Tuple(38, 16380), Tuple(39, 16380), Tuple(40, 27720), Tuple(41, 30030), Tuple(42, 32760), Tuple(43, 60060), Tuple(44, 60060), Tuple(45, 60060), Tuple(46, 60060), Tuple(47, 120120), Tuple(48, 120120), Tuple(49, 180180), Tuple(50, 180180), Tuple(51, 180180), Tuple(52, 180180), Tuple(53, 360360), Tuple(54, 360360), Tuple(55, 360360), Tuple(56, 360360), Tuple(57, 471240), Tuple(58, 510510), Tuple(59, 556920), Tuple(60, 1021020), Tuple(61, 1021020), Tuple(62, 1141140), Tuple(63, 1141140), Tuple(64, 2042040), Tuple(65, 2042040), Tuple(66, 3063060), Tuple(67, 3063060), Tuple(68, 3423420), Tuple(69, 3423420), Tuple(70, 6126120), Tuple(71, 6126120), Tuple(72, 6846840), Tuple(73, 6846840), Tuple(74, 6846840), Tuple(75, 6846840), Tuple(76, 8953560), Tuple(77, 9699690), Tuple(78, 12252240), Tuple(79, 19399380), Tuple(80, 19399380), Tuple(81, 19399380), Tuple(82, 19399380), Tuple(83, 38798760), Tuple(84, 38798760), Tuple(85, 58198140), Tuple(86, 58198140), Tuple(87, 58198140), Tuple(88, 58198140), Tuple(89, 116396280), Tuple(90, 116396280), Tuple(91, 116396280), Tuple(92, 116396280), Tuple(93, 140900760), Tuple(94, 140900760), Tuple(95, 157477320), Tuple(96, 157477320), Tuple(97, 232792560), Tuple(98, 232792560), Tuple(99, 232792560), Tuple(100, 232792560))))

7932c3

g(n) = \max \left\{ \operatorname{lcm}\!\left({s}_{1}, \ldots, {s}_{k}\right) : k \in \mathbb{Z}_{\ge 0} \;\mathbin{\operatorname{and}}\; {s}_{i} \in \mathbb{Z}_{\ge 1} \;\mathbin{\operatorname{and}}\; \sum_{i=1}^{k} {s}_{i} = n \right\}

Assumptions:

n \in \mathbb{Z}_{\ge 1}

TeX:

g(n) = \max \left\{ \operatorname{lcm}\!\left({s}_{1}, \ldots, {s}_{k}\right) : k \in \mathbb{Z}_{\ge 0} \;\mathbin{\operatorname{and}}\; {s}_{i} \in \mathbb{Z}_{\ge 1} \;\mathbin{\operatorname{and}}\; \sum_{i=1}^{k} {s}_{i} = n \right\}

n \in \mathbb{Z}_{\ge 1}

Definitions:

Fungrim symbol	Notation	Short description
`LandauG`	$g(n)$	Landau's function
`Maximum`	$\mathop{\max}\limits_{x \in S} f(x)$	Maximum value of a set or function
`LCM`	$\operatorname{lcm}\!\left(a, b\right)$	Least common multiple
`ZZGreaterEqual`	$\mathbb{Z}_{\ge n}$	Integers greater than or equal to n
`Sum`	$\sum_{n} f(n)$	Sum

Source code for this entry:

Entry(ID("7932c3"),
    Formula(Equal(LandauG(n), Maximum(Set(LCM(Subscript(s, 1), Ellipsis, Subscript(s, k)), For(Tuple(k, Subscript(s, i))), And(Element(k, ZZGreaterEqual(0)), Element(Subscript(s, i), ZZGreaterEqual(1)), Equal(Sum(Subscript(s, i), For(i, 1, k)), n)))))),
    Variables(n),
    Assumptions(Element(n, ZZGreaterEqual(1))))

a3ab2a

\lim_{n \to \infty} \frac{\log\!\left(g(n)\right)}{\sqrt{n \log(n)}} = 1

TeX:

\lim_{n \to \infty} \frac{\log\!\left(g(n)\right)}{\sqrt{n \log(n)}} = 1

Definitions:

Fungrim symbol	Notation	Short description
`SequenceLimit`	$\lim_{n \to a} f(n)$	Limiting value of sequence
`Log`	$\log(z)$	Natural logarithm
`LandauG`	$g(n)$	Landau's function
`Sqrt`	$\sqrt{z}$	Principal square root
`Infinity`	$\infty$	Positive infinity

Source code for this entry:

Entry(ID("a3ab2a"),
    Formula(Equal(SequenceLimit(Div(Log(LandauG(n)), Sqrt(Mul(n, Log(n)))), For(n, Infinity)), 1)))

9697b8

\log\!\left(g(n)\right) \le \sqrt{n \log(n)} \left(1 + \frac{\log\!\left(\log(n)\right) - 0.975}{2 \log(n)}\right)

Assumptions:

n \in \mathbb{Z}_{\ge 4}

References:

Jean-Pierre Massias, Jean-Louis Nicolas and Guy Robin (1989), Effective bounds for the maximal order of an element in the symmetric group, Mathematics of Computation, 53, 118, 665--665, https://doi.org/10.1090/s0025-5718-1989-0979940-4

TeX:

\log\!\left(g(n)\right) \le \sqrt{n \log(n)} \left(1 + \frac{\log\!\left(\log(n)\right) - 0.975}{2 \log(n)}\right)

n \in \mathbb{Z}_{\ge 4}

Definitions:

Fungrim symbol	Notation	Short description
`Log`	$\log(z)$	Natural logarithm
`LandauG`	$g(n)$	Landau's function
`Sqrt`	$\sqrt{z}$	Principal square root
`ZZGreaterEqual`	$\mathbb{Z}_{\ge n}$	Integers greater than or equal to n

Source code for this entry:

Entry(ID("9697b8"),
    Formula(LessEqual(Log(LandauG(n)), Mul(Sqrt(Mul(n, Log(n))), Add(1, Div(Sub(Log(Log(n)), Decimal("0.975")), Mul(2, Log(n))))))),
    Variables(n),
    Assumptions(Element(n, ZZGreaterEqual(4))),
    References("Jean-Pierre Massias, Jean-Louis Nicolas and Guy Robin (1989), Effective bounds for the maximal order of an element in the symmetric group, Mathematics of Computation, 53, 118, 665--665, https://doi.org/10.1090/s0025-5718-1989-0979940-4"))

3d5019

\log\!\left(g(n)\right) \ge \sqrt{n \log(n)}

Assumptions:

n \in \mathbb{Z}_{\ge 906}

References:

Jean-Pierre Massias, Jean-Louis Nicolas and Guy Robin (1989), Effective bounds for the maximal order of an element in the symmetric group, Mathematics of Computation, 53, 118, pp. 665-665, https://doi.org/10.1090/s0025-5718-1989-0979940-4

TeX:

\log\!\left(g(n)\right) \ge \sqrt{n \log(n)}

n \in \mathbb{Z}_{\ge 906}

Definitions:

Fungrim symbol	Notation	Short description
`Log`	$\log(z)$	Natural logarithm
`LandauG`	$g(n)$	Landau's function
`Sqrt`	$\sqrt{z}$	Principal square root
`ZZGreaterEqual`	$\mathbb{Z}_{\ge n}$	Integers greater than or equal to n

Source code for this entry:

Entry(ID("3d5019"),
    Formula(GreaterEqual(Log(LandauG(n)), Sqrt(Mul(n, Log(n))))),
    Variables(n),
    Assumptions(Element(n, ZZGreaterEqual(906))),
    References("Jean-Pierre Massias, Jean-Louis Nicolas and Guy Robin (1989), Effective bounds for the maximal order of an element in the symmetric group, Mathematics of Computation, 53, 118, pp. 665-665, https://doi.org/10.1090/s0025-5718-1989-0979940-4"))

87d19b

\max \left\{ p : p \in \mathbb{P} \;\mathbin{\operatorname{and}}\; p \mid g(n) \right\} \le 1.328 \sqrt{n \log(n)}

Assumptions:

n \in \mathbb{Z}_{\ge 5}

References:

Jon Grantham (1995), The largest prime dividing the maximal order of an element of S_n, 64, 209, pp. 407--210, https://doi.org/10.2307/2153344

TeX:

\max \left\{ p : p \in \mathbb{P} \;\mathbin{\operatorname{and}}\; p \mid g(n) \right\} \le 1.328 \sqrt{n \log(n)}

n \in \mathbb{Z}_{\ge 5}

Definitions:

Fungrim symbol	Notation	Short description
`Maximum`	$\mathop{\max}\limits_{x \in S} f(x)$	Maximum value of a set or function
`PP`	$\mathbb{P}$	Prime numbers
`LandauG`	$g(n)$	Landau's function
`Sqrt`	$\sqrt{z}$	Principal square root
`Log`	$\log(z)$	Natural logarithm
`ZZGreaterEqual`	$\mathbb{Z}_{\ge n}$	Integers greater than or equal to n

Source code for this entry:

Entry(ID("87d19b"),
    Formula(LessEqual(Maximum(Set(p, For(p), And(Element(p, PP), Divides(p, LandauG(n))))), Mul(Decimal("1.328"), Sqrt(Mul(n, Log(n)))))),
    Variables(n),
    Assumptions(Element(n, ZZGreaterEqual(5))),
    References("Jon Grantham (1995), The largest prime dividing the maximal order of an element of S_n, 64, 209, pp. 407--210, https://doi.org/10.2307/2153344"))

65fa9f

\left(\operatorname{RH}\right) \iff \left(\log\!\left(g(n)\right) < \sqrt{f(n)} \;\text{ for all } n \in \mathbb{Z}_{\ge 1}\; \text{ where } f(y) = \mathop{\operatorname{solution*}\,}\limits_{x \in \left(1, \infty\right)} \left[\operatorname{li}(x) = y\right]\right)

References:

Marc Deleglise, Jean-Louis Nicolas, The Landau function and the Riemann Hypothesis, https://arxiv.org/abs/1907.07664

TeX:

\left(\operatorname{RH}\right) \iff \left(\log\!\left(g(n)\right) < \sqrt{f(n)} \;\text{ for all } n \in \mathbb{Z}_{\ge 1}\; \text{ where } f(y) = \mathop{\operatorname{solution*}\,}\limits_{x \in \left(1, \infty\right)} \left[\operatorname{li}(x) = y\right]\right)

Definitions:

Fungrim symbol	Notation	Short description
`RiemannHypothesis`	$\operatorname{RH}$	Riemann hypothesis
`Log`	$\log(z)$	Natural logarithm
`LandauG`	$g(n)$	Landau's function
`Sqrt`	$\sqrt{z}$	Principal square root
`ZZGreaterEqual`	$\mathbb{Z}_{\ge n}$	Integers greater than or equal to n
`UniqueSolution`	$\mathop{\operatorname{solution*}\,}\limits_{x \in S} Q(x)$	Unique solution
`LogIntegral`	$\operatorname{li}(z)$	Logarithmic integral
`OpenInterval`	$\left(a, b\right)$	Open interval
`Infinity`	$\infty$	Positive infinity

Source code for this entry:

Entry(ID("65fa9f"),
    Formula(Equivalent(RiemannHypothesis, Where(All(Less(Log(LandauG(n)), Sqrt(f(n))), ForElement(n, ZZGreaterEqual(1))), Equal(f(y), UniqueSolution(Brackets(Equal(LogIntegral(x), y)), ForElement(x, OpenInterval(1, Infinity))))))),
    References("Marc Deleglise, Jean-Louis Nicolas, The Landau function and the Riemann Hypothesis, https://arxiv.org/abs/1907.07664"))

Definitions

Tables

Arithmetic representations

Asymptotics

Bounds and inequalities

Riemann hypothesis