Introduction to qSpoces

What are qSpaces?

qSpaces are directed
graphs comprised of vertices and edges (also known as nodes and arcs).
There is a qSpace for every prime number, designated with the letter q.
For example, q7 is the qSpace generated by the prime number 7.
Similarly there are these qSpaces: q17, q103, q54882521, etc.

Each qSpace is infinite in size, since the vertices in any qSpace are the set of
prime numbers.

How are qSpaces formed?

The generating
function for any qSpace is the function:

qs(p,q)=r,

such that
p, q &
r are all prime,

where
qs(p,q)
= max(prdc(p*q+1)),

where
prdc(n)
is the set of prime
factors of n,

and
max(s)
is the largest value
in the set s.

For example,
qs(13,7)=23 because
13*7+1 = 92,

and
prdc(92)={2,2,23},
and
max{2,2,23}=23.

Continuing this example,
qs(23,7)=3 because
23*7+1 = 162, and
prdc(162)={2,3,3,3,3},
and
max{2,3,3,3,3}=3.

Therefore, in
q7 there is an edge from vertex
13 to vertex
23; and there is another edge from
23
to
3.

It is immediately clear that ever y qSpace is unique.
While in
q7 there is an edge from
13
to
23,
in
q29
there is an edge from
13
to
3,
and an edge from
23
to
167.

Some properties of qSpaces

Since the function
qs is defined for all
primes,
p;
and the function yields a unique value for all input parameters, every vertex
has exactly one from-edge. We say
that each vertex has exactly one (unique) successor.
Not immediately obvious is the fact that some vertices have many
predecessor.

For example, vertices 59, 151, 197 (and many others), are all immediate
predecessors of 23.

Some interesting consequences

Perhaps the most
surprising result from early exploration of the qSpaces, is that is seems that
every qSpace has at least one cycle.
For example, in q7 we find this cycle:

3 -> 11 -> 13 -> 23 -> 3

And, in q13 we find
two cycles:

19 -> 31 -> 101 -> 73 ->
19

This hypothesis has
been tested and confirmed for the first 1 million primes.
Click here to see other examples of cycles in qSpaces.
At this point one might feel ready to call this working hypothesis a
conjecture.

qSpace Conjecture

Every qSpace has at
least one cycle.

Interesting graphs

When the partial
graphs of some of the vertices of a qSpace are displayed using graph
visualization software, interesting forms and shapes result.
Click here to see some of those graphical structures.

Since there are an infinite number of primes, it is not possible to show an
entire qSpace, since every qSpace has an infinite number of verices and edges.

cqSpaces

In the qs function
described above both p and q are prime numbers.
It is possible to relax that requirement and define a cqs function:

cqs(cp,q)=r,

such that
q & r
are prime, but
cp
can be either prime or composite,

where
qs(cp,q) = max(prdc(cp*q+1)),

where
prdc(n)
is the set of prime
factors of n,

and
max(s)
is the largest value
in the set s.

Predecessorship

One of the advantages
of considering cqSpaces is that it permits a simpler definition of
predecessorship. In cqSpace, if
cp is a predecessor
of
r
in
q,
then
r|cpq+1 since
r
Î
prdc(cpq+1).
Thus,
r|q(cp+rk)+1, for all
k>0
r; and
r
Î
prdc(q(cp+rk)+1).
And, if
r is the maximum integer in
prdc(q(cp+kr)+1),
then
cp+kr
is a predecessor of
r; otherwise, it is
not a predecessor.

For example, in
q7, since cqs(3,7)=11,

11
Î
prdc(7(3+11k)+1).
We find in some cases that 11 is the maximum element of the prdc; in other cases
it is not. Thus,
cqs(3+11,7)=11, cqs(3+22,7)=11,
and
cqs(3+44,7)=11; but,
cqs(3+33,7)=23, cqs(3+55,7)=37,
and
cqs(3+77,7)=17.

This fact allows us to quickly find predecessors of 11 in q7.
p is a predecessor of
11 in
q7 if
p=3+11k,
for
k>0,
p
is prime, and
11
is the maximum element in
prdc(7p+1).
Thus, 47, 113, 157, 311, and 509 are all predecessors of 11 in q7; but
179, 223, 421, 443, and 487 are not.

Ancestorship – i.e., sequence of subsequent predecessors

We saw above that if p
is a predecessor of r in q, then r|pq+1;i.e.,
p*q%r=1. Since
q
and
r
are both prime, we know that
k*q%r
will take on all the
values between 0 and r-1 as k goes from 0 to r-1.
In other words, it takes at most r probes to find an integer, k, either
prime or composite, such that
r|pq+1; in other
words, to find a predecessor for r in cqSpace.

And, from the discussion of predecessorship, we can use a predecessor in
cqSpace to find a predecessor in qSpace.
This raises the question: Given a vertex at some prime, r, can we
generate an unbounded sequence of ancestors of r?
This seems fairly likely, though the set of potential candidates gets
sparser as r gets larger.

For example, in
q7, let us produce a sequence of ancestors of 11 in q7.
We start with 3 -> 11.
Operating first in cqSpace, we find that 2*7%3=1, 5*7%3=1, 8*7%3=1, etc.
So, we try these values and find that cqs(5,7) = qcs(23,7) = cqs(41,7) =
cqs(104,7) = cqs(185,7) = 3.
Transitioning back to qSpace, we
find that 5, 23 and 41 are all ancestors of 3.
Since 23 is in the cycle of q7, we use 5 instead.
So we have:

5 -> 3 -> 11

Continuing this
process, we then find qs(2,q)=5. So
we have:

2 -> 5 -> 3 -> 11

And, after more
iterations, we have:

929 -> 271 -> 73 -> 2 -> 5 -> 3 -> 11

Stub nodes

Since
r=max(prdc(pq+1) it
is clear that
r
is in the set
prdc(pq+1); thus
r|pq+1.
From this we can see that q has no predecessors in qSpace; otherwise we
would have q|pq+1.

We can call vertices (or nodes) which have no predecessors
*stub nodes*.
And we can ask, are there any other stub nodes in qSpace for given q.

What about
2? In order for
2 to be
max(prdc(pq+1)), the prdc must be
{2, 2, . . , 2};
i.e.,
prdc(pq+1)=2^{n}.
Therefore,
pq=2^{n}-1. Can that condition be met for all qSpaces?

qkSpaces

What would happen if
we used an arbitrary integer, k, in place of 1 in the basic qSpace function?
In other words, we define:

qks(p,q,k)=r,

such that
p, q &
r are prime, and
k is any integer
>1 ,

where
qks(p,q,k) = max(prdc(p*q+k)),

where
prdc(n)
is the set of prime
factors of n,

and
max(s)
is the largest value
in the set s.

It turns out that at least some of the resulting qkSpaces also have cycles.
For example, in q7-5 we find this cycle:

41 -> 73 -> 43 -> 17 ->
31 -> 37 -> 11 -> 41

And, in q5-4 we find
this cycle:

17 -> 89 -> 449 -> 173 -> 79 -> 19 -> 11 -> 59 -> 17

Explorations, questios & challenges

Within these qSpaces
there are many avenues to explore, many questions to answer and many challenges
to take on. Here are some examples.

– what causes cycling?

– are there other stub
nodes?

– can a predecessor for 2 be
found in all qSpaces except q2?

– are there cycles for
all (or most) q-k combinations?

– challenge: find the
longest cycle

– challenge: find a
qSpace that has no cycles

– challenge: generate
the longest branch in a given qSpace