order of a function =/= p-1

[bhelmes]

A peaceful night for all persons,


i am looking for an algebraic structure which has not an order as p-1 or p+1

What about

(r 1)(x) = f(x,y) mod p where r is element N and p prime.
(0 r )(y)

Would be nice to get a short link about this topic.


Greetings from the algebraic structures,

there seems to be more than expected
Bernhard

[CRGreathouse]

I'm so confused by this question.

You're looking for an algebraic structure A, that is, a set S and a collection O1, O2, O3, ..., On of operators on S. You then want A to have an order other than p-1 or p+1, but what do you mean by "order" and what is p?

It sounds like p is some fixed prime number and your set is {0, 1, ..., p-1}, with your operations being some "natural" operation or operations mod p. If your operations are unary, each element of S has an order; perhaps you mean the exponent of the group so induced. Since this divides the order of the group, that is, p, it can't be equal p+1 and can equal p-1 only if p = 2. Otherwise, please clarify what you mean.

[paulunderwood]

I too was confused. I think Bernhard means f(x,y) = [1,r;0,1]*[x,y]~ in pari-speak. HTH.

[CRGreathouse]

Originally Posted by paulunderwood

I too was confused. I think Bernhard means f(x,y) = [1,r;0,1]*[x,y]~ in pari-speak. HTH.

In which case f(x, y) is the column vector [x + r*y; y], where r is (apparently) some fixed but unspecified natural number.

[bhelmes]

A peaceful and pleasant night for everyone,


if i have a function f(x) mod p, where p is a prime and x is element 0 ... p-1
and the function should have as result a natural number from 0 to p-1
then there will be a cycle of function terms.


f(x) : Np -> Np



The amount of results of f(x) is limited, therefore if i make a recursion,
there has to be a repetition of f(x).


i take an x0, calculate x1=f(x0) mod p, calculate x2=f(x1) mod p and so on



I thought that the expression "order" describes the huge of the cylic structure.


For example, you could take a 2x2-matrix A and a vector (x,y)
and consider the function f(x,y)=A(x,y) mod p
where the mod p is taken for every x and y


The question was,

if A=[r,1;r,0] so that the eigenwert is r, what will be the huge of the cyclic
structure ?



I will try to improve my mathematical english, but it is not easy for me
to explain an idea and translate it exactly in another language.


Greetings from the recursive functions

Bernhard

[CRGreathouse]

I don't see a useful way of answering that in general, it depends on the value of p, r, and the starting values of the column vector. For p = 2, r = 0 you get order 1. For p = 2, r = 1 you get 1 if you start with [2;2] and 3 otherwise, which I will denote
[3 3]
[3 1].

For p = 3, r = 0 you get order 1; for p = 3, r = 1 you get
[8 8 8]
[8 8 8]
[8 8 1];
for p = 3, r = 2 you get
[3 1 3]
[1 3 3]
[3 3 1].

For p = 5, r = 0 you get order 1; for p = 5, r = 1 you get
[20 4 20 20 20]
[20 20 20 4 20]
[ 4 20 20 20 20]
[20 20 4 20 20]
[20 20 20 20 1];
for p = 5, r = 2 you get
[24 24 24 24 24]
[24 24 24 24 24]
[24 24 24 24 24]
[24 24 24 24 24]
[24 24 24 24 1];
for p = 5, r = 3 you get
[4 4 1 4 4]
[1 4 4 4 4]
[4 4 4 1 4]
[4 1 4 4 4]
[4 4 4 4 1];
for p = 5, r = 4 you get
[3 3 3 3 3]
[3 3 3 3 3]
[3 3 3 3 3]
[3 3 3 3 3]
[3 3 3 3 1].

Code for generating these:

findCycle(ff:closure,startAt,flag=0)={
	my(power=1,len=1,tortoise=startAt,hare=ff(startAt),mu);
	while (tortoise != hare,
		if (power == len,
			tortoise = hare;
			power <<= 1;
			len = 0
		);
		hare = ff(hare);
		len++
	);

	tortoise=hare=startAt;
	for (i=1,len,
		hare = ff(hare)
	);
	while(tortoise != hare,
		tortoise=ff(tortoise);
		hare=ff(hare);
		mu++
	);
	if(flag, print("mu = "mu));
	len
};
addhelp(findCycle, "findCycle(ff, startAt): Finds the length of the first cycle that startAt, ff(startAt), ff(ff(startAt)), ... enters into. Prints the prefix length (steps taken before the cycle begins).");

f(p,r,startAt)=my(A=[r,1;r,0]);findCycle(v->A*v%p,startAt);
g(p,r)=matrix(p,p,x,y,f(p,r,[x;y]));