Partitions Based On Permutations

[Roland Bacher]

Dear seqfans,

I think a proof of the the conjecture that every 
number which is big enough can be written in
the form 
\sum_{j=1}^n j \pi(j)
for some integer n and some permutation \pi of
{1,\dots,n} 
can be elaborated along the following lines
(somewhat analogous to the approach suggested by Max):

(1) For a given n, the smallest number of this form is
a_n={n+2\choose 3}=n(n+1)(n+2)/6
and the difference
b_n=a_{n+1}-a_n
is given by b_n={n+2\choose 2}=(n+1)(n+2)/2.

It is thus enough to find suitable permutations 
\pi of {1,\dots,n}
for all integers in the range
[a_n,a_n+b_n-1].

(2) The number a_n is achieved by the "Coxeter element" c,
ie by the involution composed by all transpositions (i,n+1-i)
Composing  c with a tranposition of the form (i,i+k)$ augments the
value of the associated integer by k^2.
Since every integer is a sum of four squares by a Theorem of Lagrange
and since all we need is integers in the range 0... b_n-1~n^2/2
there should be plenty of space in order to apply Lagrange's 
theorem. More precisely, the four integers c_1,c_2,c_3,c_4 
appearing in Lagrange's theorem are all <(n+1)/\sqrt(2).
It is thus enough to show that given four natural 
non-zero integers c_1,\dots,c_4 (zeros can be dismissed)
<(n+2)/sqrt(2), there exists four integers e_1,_2,e_3,e_4
such that the eight integers 
e_1,e_1+c_1,e_2,e_2+c_2,e_3,e_3+c_3,e_4,e_4+c_4
are all distinct and in {1,...,n}.
(One modifies then the Coxeter element by
the product of the transpositions (e_i,e_i+c_i))
Putting in a little effort, I think that I can prove this for n 
huge enough. (Moreover, the proof is probably constructif 
and yields an explicit bound. So 34 is probably indeed
the last integer not representable in this way).

Best whishes,  Roland 










On Tue, Dec 04, 2007 at 10:31:17AM -0800, Leroy Quet wrote:
> I just submitted this sequence:
> 
> %I A000001
> %S A000001
> 1,0,0,1,1,0,0,0,0,1,2,0,2,1,0,0,0,0,0,1,3
> %N A000001 a(n) = the total number of
> permutations (m(1),m(2),m(3)...m(j)) of
> (1,2,3,...,j) where n = 1*m(1) + 2*m(2) + 3*m(3)
> + ...+j*m(j), where j is over all positive
> integers.
> %C A000001 Does every integer greater than some
> positive integer N have at least one such
> representation?
> %e A000001 21 has a(21)=3 such representations:
> 21 = 1*4 + 2*3 + 3*1 + 4*2 = 1*4 + 2*2 + 3*3 +
> 4*1 = 1*3 + 2*4 + 3*2 + 4*1.
> Not all representations of an integer n need to
> necessarily have the same j. For example, 91 =
> 1*1 + 2*2 + 3*3 + 4*4 + 5*5 + 6*6 (j=6). And 91
> also equals 1*7 + 2*4 + 3*5 + 4*3 + 5*6 + 6*2 +
> 7*1 (j=7).
> %O A000001 1
> %K A000001 ,more,nonn,
> 
> I know I haven't given the best definition.
> Hopefully what I mean is clear. (The examples
> should help a little.)
> 
> Does every integer greater than some integer
> (such as, say, 20) have such a representation?
> 
> It seems very likely that the answer is yes. For
> a given j, the least  possible n is j^3/6 + j^2/2
> + j/3. The greatest possible n is j^3/3 + j^2/2
> +j/6 (the sum of the first j squares).
> The difference between these extremes, plus 1, is
> j^3/6 - j/6 + 1, if I did my math right.
> But the number of permutations for a given j is
> j!, obviously.
> So the chance that any particular integer between
> the maximum n and the minimum n, for a given j,
> does not have a representation gets low pretty
> quick.
> 
> Thanks,
> Leroy Quet
> 
> 
> 
> \/\/\/\///////\\\\\\\/\/\/\/
> /\/\/\///////**\\\\\\\/\/\/\
> \/\/\///////*/\*\\\\\\\/\/\/
> /\/\/\\\\\\\*\/*///////\/\/\
> \/\/\/\\\\\\\**///////\/\/\/
> /\/\/\/\\\\\\\///////\/\/\/\
> 
> 
>       ____________________________________________________________________________________
> Looking for last minute shopping deals?  
> Find them fast with Yahoo! Search.  http://tools.search.yahoo.com/newsearch/category.php?category=shopping
> 



Consider the function f(x) = floor(x/ln(x)). Let S_k be the set of all
values {v_1, v_2... v_n} such that f(v_1) = f(v_2) = ... f(v_n) = some
constant c. For example:

S_1 = {2,3,4} because f(2) = f(3) = f(4) = 2, or c_1
S_2 = {5,6,7,8} because f(5) = f(6) = f(7) = f(8) = 3, or c_2,
S_3 = {9,10,11,12) because f(9) = f(10) = f(11) = f(12) = 4, or c_3,

and so on.

Since the number of primes less than x is always greater than x/ln(x) (by
the Prime Number Theorem), is that sufficient to show that there is at least
one prime between, say, f(4) and f(8), or f(8) and f(12)? Ideally I'd like
to show that that's the case for all of these sets; that there is one prime
between f(y) and f(z), where y is the largest value in S_a and z is the
largest value in S_(a+1). Thanks!






Someone has replied off-list with numerical results showing that this isn't
true, so it's back to the drawing board. Thanks!


-----Original Message-----

Consider the function f(x) = floor(x/ln(x)). Let S_k be the set of all
values {v_1, v_2... v_n} such that f(v_1) = f(v_2) = ... f(v_n) = some
constant c. For example:

S_1 = {2,3,4} because f(2) = f(3) = f(4) = 2, or c_1
S_2 = {5,6,7,8} because f(5) = f(6) = f(7) = f(8) = 3, or c_2,
S_3 = {9,10,11,12) because f(9) = f(10) = f(11) = f(12) = 4, or c_3,

and so on.

Since the number of primes less than x is always greater than x/ln(x) (by
the Prime Number Theorem), is that sufficient to show that there is at least
one prime between, say, f(4) and f(8), or f(8) and f(12)? Ideally I'd like
to show that that's the case for all of these sets; that there is one prime
between f(y) and f(z), where y is the largest value in S_a and z is the
largest value in S_(a+1). Thanks!







Jack Brennen:

> The interesting part is that only a=4 and a=5 are represented up to  
> this search limit. The polynomials n^2+n+1 and n^3+n+1 are much  
> "denser" up to this limit, but yield no abundant numbers yet.

Last month, I replied:

> For n^3+n+1, the smallest solution appears to be n=12210244, for  
> which n^3+n+1 = 1820425992742030417029 and sigma(n^3+n+1) =  
> 3663946628222507827200.

Just a quick follow-up... I've got 20 solutions for abundant n^3+n+1,  
from n=12210244 to n=271870216. In contrast, there are no solutions  
for abundant n^2+n+1 up to n=10^9.