User david callan - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T08:35:18Z http://mathoverflow.net/feeds/user/10363 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/77739/do-integer-valued-power-sums-imply-integer-valued-elementary-symmetric-functions Do integer-valued power sums imply integer-valued elementary symmetric functions? David Callan 2011-10-10T20:07:02Z 2011-10-10T20:07:02Z <blockquote> <p><strong>Possible Duplicate:</strong><br> <a href="http://mathoverflow.net/questions/74468/implications-of-a-relation-on-algebraic-numbers" rel="nofollow">Implications of a relation on algebraic numbers</a> </p> </blockquote> <p>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? </p> <p>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 <code>\$e_1,\ 2e_2\$ and \$2e_2^2\$</code> are all integers, from which <code>\$e_2\$</code> 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.</p> http://mathoverflow.net/questions/14863/random-alternating-permutations/43765#43765 Answer by David Callan for Random Alternating Permutations David Callan 2010-10-27T05:52:18Z 2010-10-27T06:10:50Z <p>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 <em>with first entry \$&lt; p_1\$</em>; then join them together (incrementing entries \$\ge p_1\$ in the updown permutation).</p> <p>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.</p> <p>(* e[n,k] is the Entringer number *)</p> <p>e[0,0] = 1; <BR> e[n_,0]/;n>=1 := 0; <BR> e[n_,k_]/;k>n || k&lt;0 := 0 <BR> e[n_,k_] := e[n,k] = e[n,k-1] + e[n-1,n-k] </p> <p>ComplementPermutation[perm_] := Module[{n=Length[perm]}, n+1-perm];<BR></p> <p>incrementSpecifiedAndUp[perm_,k_]:=perm/.{i_/;i>=k :> i+1};</p> <p>partialSums[list_] := Drop[FoldList[Plus,0,list],1];</p> <p>RandomUpDownPermFirstEntryAtMostk[n_,k_]/;k==n :=<br> RandomUpDownPermFirstEntryAtMostk[n,n-1];<BR> RandomUpDownPermFirstEntryAtMostk[n_,k_]/;1&lt;=k&lt;n := <BR> ComplementPermutation[RandomDownUpPermFirstEntryAtLeastk[n,n+1-k]]</p> <p>RandomDownUpPermFirstEntryAtLeastk[1,1]={1}; RandomDownUpPermFirstEntryAtLeastk[2,2]={2,1};</p> <p>RandomDownUpPermFirstEntryAtLeastk[n_,k_]/; n>=3 &amp;&amp; 2&lt;=k&lt;=n := Module[{keys,m,i,firstEntry,restOfPerm},</p> <p>(* pick first entry using the Entringer distribution *)<BR> keys=partialSums[Table[e[n-1,j],{j,k-1,n-1}]];<BR> m=Random[Integer,{1,Last[keys]}];<BR> i=1;<BR> While[Not[ m&lt;=keys[[i]] ],i=i+1];<BR> firstEntry=k-1+i;<BR></p> <p>(* choose restOfPerm uniformly from updowns with <em>their</em> first entry &lt; firstEntry *)<BR> restOfPerm=RandomUpDownPermFirstEntryAtMostk[n-1,k-2+i];<BR></p> <p>(* amalgamate firstEntry and restOfPerm *)<BR> Join[{firstEntry},incrementSpecifiedAndUp[restOfPerm,firstEntry]] ]<BR></p> <p>RandomDownUpPerm[1]={1};<BR> RandomDownUpPerm[n_]/;n>=2 := RandomDownUpPermFirstEntryAtLeastk[n,2]<BR></p> <p>Sample output:<BR> In[264]:=RandomDownUpPerm[15]<BR> Out[264]=<BR> {8, 2, 4, 1, 15, 6, 7, 3, 10, 9, 13, 11, 14, 5, 12}</p>