1,3,10,30,91

From: Luka Lasic (llasic_at_fkit.hr)
Date: 02/17/05 

Date: 17 Feb 2005 10:45:01 -0500

Hi,

I have the following problem:

Let the sets A(n), n>=3, be defined in the following way:

A(3):={{0,1,2),(0,2,1),(1,0,2),(1,2,0),(2,0,1),(2,1,0)}

Now lets construct A(4). We take all of the elements of A(3) and for
each one of them we construct six elements of A(4) in this way: 0
appearing in the chosen element of A(3) is substituted by "1,2" or
"2,1" (this creates two elements of A(4)), then 1 appearing in the
same chosen element of A(3) is substituted by "0,2" or "2,0" (this
creates two additional elements of A(4)), and at last 2 appearing in
the same chosen element of A(3) is substituted with "0,1" or "1,0"
(this creates the last two elements of A(4) made out of the chosen
element of A(3)). This procedure is repeated with ALL of the elements
of A(3).

For example, we take (1,2,0) and construct (0,2,2,0), (2,0,2,0),
(1,0,1,0), (1,1,0,0), (1,2,1,2), and (1,2,2,1) as elements of A(4).
This is done with ALL of the elements of A(3). Thus we get A(4) which
would consist of 36 elements altogether. But, some of the elements of
A(4) obtained by this construction appear to be the same; if we cancel
the doubles out, we finally get to A(4) containing 18 elements.

A short generic definition of A(4) would now be:
          
A(4)={p(0,0,1,1):p element of S(3)} U {p(0,1,0,1):p element of S(3)} U
{p(0,1,1,0):p element of S(3)}

We see that A(3) is basically one class of equivalence of S(3), while
A(4) is a union of three such equivalence classes. For example, class
{p(0,1,1,0):p element of
S(3)}={{0,1,1,0},{0,2,2,0},{1,0,0,1},{1,2,2,1},{2,0,0,2},{2,1,1,2}} is
one of the three equiv. classes of A(4).

We see that all of the sets A(n) consists of ordered n-tuples. Up to
the equiv. classes, the cardinalities of these sets are:

c(A(3))=1=3^0
c(A(4))=3=3^1
c(A(5))=10=3^0+3^2
c(A(6))=30=3^1+3^3
c(A(7))=91=3^0+3^2+3^4
c(A(8))=273=3^1+3^3+3^5
etc.

Conjecture: c(A(n)) = the cardinality of the set of all non-zero
quadratic residues modulo 3^(n-2).

Question 1: does there exist a canonical bijection between the two
sets in question?

Question 2: what could one say about a graph structure (??) for equiv.
classes of A(n)?

Best regards,

Luka