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

On Wed, 7 Jan 2009 12:06:02 -0800 (PST), scattered
<former_schizoid@xxxxxxxxxxx> wrote:

On Jan 7, 2:29 pm, quasi <qu...@xxxxxxxx> wrote:
On Wed, 7 Jan 2009 11:05:08 -0800 (PST), scattered

<former_schiz...@xxxxxxxxxxx> wrote:
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?

Yes. Permutations commute with the polynomial termwise maps, so you
might as well do them first.

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.

Also, if q is on the outside, it can be brought inside.

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].

Yes.

I suspect that the answer is "no" but don't have much
to base that hunch on.

Actually, I suspect the answer is "yes" (based on an intuitive idea as
to how to actually construct such a finite generating set), but at
this point, I'm not very certain.

It is an interesting problem. I wouldn't bet any money on my hunch
being correct. In fact, I just noticed that the answer is trivially
"yes" for n = 2 since then {[0,1]} itself is a generating set (and you
can get by with linear polynomials).

Right.

Have you looked at the case n = 3 explicitly?

No, I thought about it briefly and convinced myself (using an
intuitive quasi-proof) that the answer is "yes" for n = 3. I had
planned to do some work on the case n = 4, which I felt was the
make-or-break prototype case, but I haven't had the chance yet.

But I really should dispatch n = 3 first, with an actual proof. I'll
look at it.

A wild guess based on the above is that the set of all
points [x,y] with x,y in {0,1,2} might work

Yes, that was my intuitive sense as well. But as previously noted,
even if that works for n = 3, it won't work for n = 4. One generator
(up to permutations) won't suffice when n > 3.

although I don't think you
would be able to restrict yourself to quadratics.

In other words, the minimal degree interpolation won't work, since the
coefficients might not be integers. But even with the permuted
possibilities? Can all 6 minimal degree interpolations fail to yield
integer polynomials? I'll check that. Even if it's the case that for n
= 3, quadratics are not enough, I would guess that there is some least
degree which always suffices. I'll play with that as well.

Sill, as I mentioned before, my sense is that the case n = 3 will work
out fairly easily (but still, we should do it), and that the first
important case to understand (if we're looking at specific cases) is
the case n = 4.

quasi
.

Relevant Pages