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

On Wed, 7 Jan 2009 07:50:59 -0800 (PST), galathaea
<galathaea@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].

quasi
.

Relevant Pages