Monday, October 5, 2009

Elementary symmetric functions of the first natural numbers

About a month ago, my good friends Esteban and José Carlos were working in a really interesting problem in number theory involving harmonic series of sequences of something that they called the Esteban primes for $p_0$.

They were (or are, I hope) trying to find out if a particular series involving this sequences of primes, converges or not. They told me about the problem, and as always, I got really interested by this strange problem relating primes and analysis.

After working out a little bit the series, one can show that it is equivalent to prove that some infinite product converges to a nonzero value. Working with these expressions, I ended up looking at polynomials of the form

$p(x)=\prod_{k=1}^n (p_k-x)$

where the $p_k$ are primes. So, at first, I tried to not work with primes directly, but with the natural numbers $1,2,3,\dots,n$ so the polynomial will be

$p(x)=\prod_{k=1}^n (k-x)$

Expanding out this polynomial gives, by Cardano equations,

$p(x)=\sum_{k=0}^n (-1)^k s_{n-k} x^{k}$

were the $s_k$ are the elementary functions for $1,2,3\dots,n$, that are given by the sum of all possible $k$ products of these numbers, so for instance, $s_n=n!$, $s_1=1+2+\dots+n$ and $s_0=1$.

Therefore, evaluating $p(1)$ we have that $p(1)=\sum_{k=0}^n (-1)^k s_{n-k}=0 $ and hence, the sum of the even elementary functions is equal to the sum of the odd ones.

For example, $n=3$ gives

$s_2=1\cdot 2+1\cdot 3+2\cdot 3=11$
$s_3=1\cdot 2\cdot 3=6$

and the result is


This reminds me of the property of the Binomial coefficients and must be somehow related, because these count the number of subsets with cardinality $k$, that is, for each subset of size $k$, we correspond to it a 1, then we add this results and that is $\binom{n}{k}$, while for the symmetric functions, for each subset of size $k$, we correspond to it the product of its elements, and then add over all subsets, and that gives $s_k$.

In other words, let $S=\{1,2,3,\dots,n\}$ and let $f$ be a function defined on the subsets of $S$.

If $f(A)=1$, for all $A\subset S$, we have that

$\binom{n}{k}=\sum_{A\subset S, |A|=k}f(A)$

on the other hand, if we define $f(A)=\prod_{k\in A} k$, then

$s_k=\sum_{A\subset S, |A|=k}f(A)$

so both forms have the same structure. I don't know what is the underlying property of such $f$ functions, so that the sum of the evens equals the sum of the odd ones, but I find it really interesting.


  1. Now we are trying to find a special Esteban's prime sequence to call it the "optimum prime sequence"... for no particular reason whatsoever (ºJª).