Do integer-valued power sums imply integer-valued elementary symmetric functions?

2011-10-10T20:07:02Z

Possible Duplicate:
Implications of a relation on algebraic numbers

If the elementary symmetric functions $e_k$ of $n$ complex variables are all integers, then all of the power sums are integers. Is the converse true?

It seems quite likely that the answer is in the affirmative. When $n=2$, for instance, Newton's identities for $k=1,2$ and $4$ yield in turn that $e_1,\ 2e_2$ and $2e_2^2$ are all integers, from which $e_2$ is also an integer. Similar ad hoc considerations, with the help of a computer program, work at least up to $n=12$. For n=3, the integrality of the first 6 power sums suffices, but for n=4 I had to consider the first 16 power sums.

Answer by David Callan for Random Alternating Permutations

2010-10-27T05:52:18Z

Below is Mathematica code based on Igor Pak's answer. To get a random downup permutation on $[n]$, start by choosing the first entry $p_1$ with the appropriate probability; then randomly choose an updown permutation of size $n-1$ from the updown permutations with first entry $< p_1$; then join them together (incrementing entries $\ge p_1$ in the updown permutation).

To implement this method, we actually need code to generate a random downup permutation with first entry $\ge$ a specified number $k$ and the code below does so. It uses the ComplementPermutation operation to interchange updown and downup permutations.

(* e[n,k] is the Entringer number *)

e[0,0] = 1;
e[n_,0]/;n>=1 := 0;
e[n_,k_]/;k>n || k<0 := 0
e[n_,k_] := e[n,k] = e[n,k-1] + e[n-1,n-k]

ComplementPermutation[perm_] := Module[{n=Length[perm]}, n+1-perm];

incrementSpecifiedAndUp[perm_,k_]:=perm/.{i_/;i>=k :> i+1};

partialSums[list_] := Drop[FoldList[Plus,0,list],1];

RandomUpDownPermFirstEntryAtMostk[n_,k_]/;k==n :=
RandomUpDownPermFirstEntryAtMostk[n,n-1];
RandomUpDownPermFirstEntryAtMostk[n_,k_]/;1<=k<n :=
ComplementPermutation[RandomDownUpPermFirstEntryAtLeastk[n,n+1-k]]

RandomDownUpPermFirstEntryAtLeastk[1,1]={1}; RandomDownUpPermFirstEntryAtLeastk[2,2]={2,1};

RandomDownUpPermFirstEntryAtLeastk[n_,k_]/; n>=3 && 2<=k<=n := Module[{keys,m,i,firstEntry,restOfPerm},

(* pick first entry using the Entringer distribution *)
keys=partialSums[Table[e[n-1,j],{j,k-1,n-1}]];
m=Random[Integer,{1,Last[keys]}];
i=1;
While[Not[ m<=keys[[i]] ],i=i+1];
firstEntry=k-1+i;

(* choose restOfPerm uniformly from updowns with their first entry < firstEntry *)
restOfPerm=RandomUpDownPermFirstEntryAtMostk[n-1,k-2+i];

(* amalgamate firstEntry and restOfPerm *)
Join[{firstEntry},incrementSpecifiedAndUp[restOfPerm,firstEntry]] ]

RandomDownUpPerm[1]={1};
RandomDownUpPerm[n_]/;n>=2 := RandomDownUpPermFirstEntryAtLeastk[n,2]

Sample output:
In[264]:=RandomDownUpPerm[15]
Out[264]=
{8, 2, 4, 1, 15, 6, 7, 3, 10, 9, 13, 11, 14, 5, 12}

User david callan - MathOverflow

Do integer-valued power sums imply integer-valued elementary symmetric functions?

Answer by David Callan for Random Alternating Permutations