THE 2-ADIC VALUATION OF STIRLING NUMBERS

Stirling numbers of the second kind

notation

S(n, k)

definition

number of ways to partition a set of n elements into exactly k nonempty subsets

domain

n ∈ N and 0 ≤ k ≤ n

Relationships

• subject_of_analysis → 2-adic valuation

2-adic valuation

notation

ν_2(m)

definition

highest power of 2 that divides m

Relationships

• applied_to → Stirling numbers of the second kind

Tewodros Amdeberhan

No attributes recorded.

Relationships

• author_of → THE 2-ADIC VALUATION OF STIRLING NUMBERS

Dante V Manna

No attributes recorded.

Relationships

• author_of → THE 2-ADIC VALUATION OF STIRLING NUMBERS

Victor H Moll

No attributes recorded.

Relationships

• author_of → THE 2-ADIC VALUATION OF STIRLING NUMBERS

Legendre's formula

formula

ν_p(m!) = (m - s_p(m)) / (p - 1)

specific_case_p2

ν_2(m!) = m - s_2(m)

Relationships

• provides_proof_for → Kummer's identity

Kummer's identity

formula

ν_2(m choose k) = s_2(k) + s_2(m - k) - s_2(m)

Relationships

• proved_by → Legendre's formula

sequence b_{l,m}

definition

sum from k=l to m of (2^k * binomial(2m-2k, m-k) * binomial(m+k, m) * binomial(k, l))

origin

evaluation of definite integral N_{0,4}(a; m)

Relationships

• related_to → A_{l,m}

A_{l,m}

definition

(l! / m!) * 2^{m-l} * b_{l,m}

valuation_formula

ν_2(A_{l,m}) = 3l - s_2(m + l) + s_2(m - l)

Relationships

• valuation_established_by → J. Little

J. Little

No attributes recorded.

Relationships

• established_valuation_for → A_{l,m}

H. Cohen

No attributes recorded.

Relationships

• proved_valuation_for → L_1(2^m)
• proved_valuation_for → L_2(2^m)

L_1(2^m)

valuation_formula

ν_2(L_1(2^m)) = 2^m + 2m - 4

condition

m ≥ 4

Relationships

No relationships recorded.

L_2(2^m)

valuation_formula

ν_2(L_2(2^m)) = 2^m + m - 1

condition

m ≥ 4

Relationships

No relationships recorded.

Main conjecture

description

algorithm leading to description of ν_2(S(n, k))

established_case

k = 5

Relationships

• involves_set → C_{m,j}

C_{m,j}

definition

{2^m * i + j : i ∈ N such that 2^m * i + j ≥ k}

Relationships

No relationships recorded.

class C_{m,j}

definition

Set of values $\nu_2(S(2^m i + j, k))$ for $i \in \mathbb{N}$ where $2^m i + j \ge k$

partition_property

Forms a partition of $\{n \in \mathbb{N} : n \ge k\}$ into classes modulo $2^m$

Relationships

• is_constant_if → valuation consists of a single value
• splits_into → C_{m,ij} and C_{m,ij+2^{m-1}}

  condition

  from (m-1)-level class C_{m-1,ij}

m-level

definition

Inductively defined set of classes; 1-level consists of even and odd integers $\ge k$

Relationships

• defined_by → splitting of (m-1)-level classes

Main Conjecture 1.5

subject

2-adic valuation of Stirling numbers of the second kind $S(n, k)$

parameter_definition

$m_0 = m_0(k)$ defined by $2^{m_0-1} < k \le 2^{m_0}$

model_entity_type

conjecture

Relationships

• predicts_first_constant_level → m_0 - 1

  detail

  Each class belongs to the j-level for $1 \le j \le m_0 - 2$

• predicts_class_count → 2^{m_0-2}

  condition

  for any $m \ge m_0$

  detail

  Each class generates a unique, non-constant class for the (m+1)-level.

S(n, 11)

k_value

11

m_0_value

4

m_0_justification

$2^3 < 11 \le 2^4$

model_entity_type

example_case

Relationships

• predicted_first_constant_level → 3-level
• predicted_classes_per_level → 4

  condition

  for levels $m \ge 4$

• 2_level_status → non-constant

  classes

  C_{2,0}, C_{2,1}, C_{2,2}, C_{2,3}

• 3_level_valuations → C_{3,3}, C_{3,5} have valuation {0}; C_{3,4}, C_{3,6} have valuation {1}

Lengyel-De Wannemacker result

formula

$\nu_2(S(2^n, k)) = s_2(k) - 1$

condition

independent of n

definition_s_2

$s_2(k)$ is the sum of binary digits of k

model_entity_type

theorem

Relationships

• derived_from → Legendre's result

  equivalence

  $\nu_2(S(2^n, k)) = \nu_2(2^{k-1}/k!)$

• companion_formula → $\nu_2(S(2^n + 1, k + 1)) = s_2(k) - 1$

  derivation

  Using recurrence $S(2^n + 1, k + 1) = S(2^n, k) + (k + 1)S(2^n, k + 1)$

De Wannemacker inequality

formula

$\nu_2(S(n, k)) \ge s_2(k) - s_2(n)$

condition

$0 \le k \le n$

model_entity_type

theorem

Relationships

No relationships recorded.

Stirling numbers of order 1

formula

$S(n, 1) = 1$ for all $n \in \mathbb{N}$

model_entity_type

mathematical_object

Relationships

No relationships recorded.

Stirling numbers of order 3

formula

$S(n, 3) = \frac{1}{2}(3^{n-1} - 2^n + 1)$

valuation_rule

$\nu_2(S(n, 3)) = 0$ if n is odd, 1 if n is even

model_entity_type

mathematical_object

Relationships

• derived_via → recurrence iteration

  intermediate_step

  $2^{n-1} = S(n, 3) - \sum_{k=1}^{N-1} 3^k(2^{n-k}-1) - 3^N S(n-N, 3)$

Stirling numbers of the second kind S(n, 3)

valuation_rule

0 if n is odd, 1 if n is even

Relationships

• derived_from → recurrence (1.29)
• proven_via → ultrametric inequality

ultrametric inequality

formula

ν_2(x1 + x2) ≥ Min {ν_2(x1), ν_2(x2)}

strictness_condition

strict unless ν_2(x1) = ν_2(x2)

Relationships

• equivalent_to → equation (1.6)

Stirling numbers of the second kind S(n, 4)

explicit_formula

1/6 (4^(n-1) - 3^n - 3*2^(n+1) - 1)

valuation_rule

1 if n is odd, 0 if n is even

Relationships

• derived_from → equation (1.27)

Stirling numbers of the second kind S(n, 5)

explicit_formula

1/24 (5^(n-1) - 4^n + 2*3^n - 2^(n+1) + 1)

complexity

valuation is not easy to compute compared to k=3 and k=4

Relationships

• analyzed_via → m-levels

exceptional index

definition

index i where q_4i = q_4i+3

notation

q_n := ν_2(S(n, 5))

Relationships

• first_instance → i = 7

  values

  q_28 = 6, q_31 = 7

• sequence_examples → {7, 39, 71, 103, ...}

Proposition 3.5

statement

ν_2(S(8i, 5)) = 1 for all i ≥ 1

model_entity_type

finding

Relationships

• proven_using → modulo 32 analysis of 24S(8i, 5)

Proposition 3.6

statement

ν_2(S(8i + 4, 5)) ≥ 2 for all i ≥ 1

proof_method

Analysis of identity modulo 32 using congruences for powers of 2, 3, and 5

model_entity_type

theorem

Relationships

• applies_to → Stirling numbers of the second kind S(n, 5)

Lengyel's result

formula

ν_2(k!S(n, k)) = k - 1

conditions

n = a2^q, a odd, q ≥ k - 2

model_entity_type

theorem

Relationships

• implies_for_k5 → ν_2(S(n, 5)) = 1 for n = a2^q with q ≥ 3

3-level classes for k=5

composition

{C_{3,4}, C_{3,7}}

Relationships

• illustrates → Main Conjecture 1.5

Clarke's conjecture

statement

ν_p(k! S(n, k)) = ν_p(T_p(n, k))

definition_T_p

T_p(n, k) = sum_{j=0}^k (-1)^{k-j} binom(k, j) j^n, omitting j divisible by p

model_entity_type

conjecture

Relationships

• proposed_by → Clarke

Theorem 3.8

condition

Assumes Clarke's conjecture holds

formula_even_n

ν_2(S(n, 5)) = -1 + ν_2(n - u_0)

formula_odd_n

ν_2(S(n, 5)) = -1 + ν_2(n - u_1)

u_0_definition

Unique zero of f_{0,5} in 2Z_2

u_1_definition

Other zero of f_{0,5} in 1 + 2Z_2

model_entity_type

theorem

Relationships

• depends_on → Clarke's conjecture
• uses_function → f_{0,5}(x) = 5 + 10*3^x + 5^x

f_{0,6}

expression

-6 - 20*3^x - 6*5^x

model_entity_type

function

Relationships

• used_for → ν_2(S(n, 6))

f_{0,7}

expression

7 + 35*3^x + 21*5^x + 7^x

model_entity_type

function

Relationships

• used_for → ν_2(S(n, 7))

Main Conjecture for k=5

status

Proven in Section 4

parameter_m0

3

first_constant_level

2

model_entity_type

conjecture

Relationships

• established_for → Stirling numbers of the second kind S(n, 5)

Empirical approximations for ν_2(S(n, 5))

nature

Derived empirically

exception_set_I1

Indices where ν_2(S(m, 5)) ≠ ν_2(f_1(m))

exception_parity

Every third element in I_1 is odd

even_exception_progression

256m + 156

Relationships

• approximates → ν_2(S(n, 5))