Re: -- sequences of integers, closed under some operations

On Jan 7, 1:24 pm, quasi <qu...@xxxxxxxx> wrote:
On Wed, 7 Jan 2009 09:53:45 -0800 (PST), scattered





<former_schiz...@xxxxxxxxxxx> wrote:
On Jan 7, 11:58 am, quasi <qu...@xxxxxxxx> wrote:
On Wed, 7 Jan 2009 07:50:59 -0800 (PST), galathaea

<galath...@xxxxxxxxx> wrote:
On Jan 7, 5:08 am, William Elliot <ma...@xxxxxxxxxxxxxxxx> wrote:
On Wed, 7 Jan 2009, quasi wrote:
Fix a positive integer n.

Let S be the set of all sequences of n integers.

Call a subset A of S "closed" if

(1) if a is in A, then p(a) is in A, where p(a) is any permutation of a.

(2) if a is in A, then for any f in Z[x], the sequence

   f(a[1]), f(a[2]), ..., f(a[n])

is in A.

[..]

Question: Does there exist a finite subset of S whose closure is S?

The subspace of constant sequences is discrete.
If A is a subset of S and k a constant sequence of S,
then k in A iff k in permutation closure of A.

Since there are infinitely many constant sequences, the answer is no.

but the closure of any space
 containing the constant sequence C_m
 (= m, m, .., m)
also contains the constant sequence C_(m+1)
by application of f(x) = x + 1

similarly C_(m-1)

the closure of a space containing one such point
would be a space containing all such points

also:

 call this total space of constant C
 all closures will contain C

Yes, all nonempty closures.

this indicates a simple property
 of the closure of points in this space:

given a point p = p_1, p_2, .., p_n

if p has k elements of the sequence identical
then all points in the closure of p
 will have at least k elements identical

Yes.

the proof is simply noting
 that the first transform does not change this property
 and polynomials do not produce different outputs
   for the same input
 (though they may of course produce similar outputs
    for different inputs
  as in the constant polynomials or squares or ..)

so...

what is the closure of 1, 2, .., n?

Except for the definition (closed under permutations and termwise
univariate integer polynomial images), I'm not sure. However, the
closure of {[1,2, ..., n]} definitely does not contain all sequences
with n distinct elements.

For example, with n = 4, the closure of {[1,2,3,4]} does not contain
[1,2,4,6].

This is far from obvious. There are infinitely many polynomials with
rational coeffients which pass through the 4 points (1,1), (2,2),
(3,4), (4,6) - how can you be sure that none of those polynomials in
fact have integer coefficients?

Consider the images, mod 2.

The sequence [1,2,3,4] is congruent to [0,1,0,1] mod 2, so any
polynomial  image of that sequence (or any permutation of that
sequence) cannot have exactly 1 odd and 3 evens.

Nice! I was thinking in terms of systems of congruences involving the
constant term of the polynomial (e.g. f(4)=6 implies the constant term
is congruent to 6 mod 4) and saw that this system was in fact
solvable, hence my skepticism. Your argument is a nice illustration of
the power of homomorphisms.

Your argument shows that a generating set would have to have at least
n/2 elements. It seems natural to try to see what sort of mileage you
can get out of looking at things mod p for various primes p.

Am I correct in thinking that the closure of a set A consists of all
sequences of the form f(p(a)) where p(a) is a permutation and f(_) is
component-wise application of f? This seems to follow since, e.g., g(q
(f(p(a)))) = g(f(q(p(a)))) and both S_n and Z[X] are closed under
composition. If so, you might as well restrict your attention to sets
that are already closed under permutations and simply ask if there is
a finite set A with the property that everything in Z^n can be written
in the form f(a) for some a in A and f in Z[X]. I suspect that the
answer is "no" but don't have much to base that hunch on.

-scattered

.

Relevant Pages