Introduction

This Mathematica notebook is licensed under a MouseOver .

It provides software for producing the endograph of finite functions.  MouseOver gives a definition of endograph and MouseOver discusses finite endographs.

The notebook is still rough and incomplete.  It will be revised from time to time.  I hope anyone interested will feel free to improve this work and to use it in their own publications and coursework.

Definitions

SetOptions[Plot, AspectRatio -> Automatic]; 
tf := TableForm; tx := TeXForm; hh := Hold; 
  ss := Simplify; 
tt[x_] :=TraditionalForm[x]; 
  mf := MatrixForm;

RuleGraph[r_]:=GraphPlot[r,VertexLabeling->True, DirectedEdges->True,EdgeRenderingFunction->(Arrow[#1,0.1]&),PlotStyle->Directive[Arrowheads[0.02]],VertexRenderingFunction->(Text[#2,#1]&),ImageSize->Medium]

MakeFunctionRule[f_,n_]:=#->f[#]&/@ Table[k,{k,0,n-1}]

Endograph[f_,n_]:=GraphPlot[MakeFunctionRule[f,n],VertexLabeling->True,DirectedEdges->True,EdgeRenderingFunction->(Arrow[#1,0.1]&),PlotStyle->Directive[Arrowheads[0.02]],VertexRenderingFunction->(Text[#2,#1]&),ImageSize->Small]

LGraph[r_]:=LayeredGraphPlot[r,EdgeRenderingFunction->(Arrow[#1,0.1]&),PlotStyle->Directive[Arrowheads[0.03]],VertexRenderingFunction->(Text[#2,#1]&),ImageSize->Small]

DFGraph[f_,n_]:=LGraph[MakeFunctionRule[f,n]]

CographSource[n_]:=n;CographTarget[n_]:=n+100  (*See the failed experiment at the end of this notebook*)

CographFunctionRule[f_,n_]:=CographSource[#]->CographTarget[f[#]]&/@ Table[k,{k,0,n-1}]

CographLayout[n_]:=(CographSource[#]&/@Table[k,{k,0,4}])~Union~(CographTarget[#]&/@Table[k,{k,0,4}])

CR[n_]:=If[n<100,{n,2},{n-100,0}]

Lab[n_]:=If[n<100,n,n-100]

Cograph[f_,n_]:=GraphPlot[CographFunctionRule[f,n],VertexLabeling->True,DirectedEdges->True,EdgeRenderingFunction->(Arrow[#1,0.1]&),PlotStyle->Directive[Arrowheads[0.04]],VertexCoordinateRules->Evaluate[(#->CR[#])&/@ CographLayout[n]],VertexRenderingFunction->(Text[Lab[#2],#1]&),ImageSize->Small]

f1[n_]:=Mod[n+1,5];f2[n_]:=Mod[n^2,5];

t2[1]:=2;t2[2]:=4;t2[4]:=1;t2[3]:=0;t2[0]:=3;t2[n_]:=n

Some Checking

CographFunctionRule[t2,5]

CographSource[#]&/@Table[k,{k,0,4}]

CographTarget[#]&/@Table[k,{k,0,4}]

CographLayout[5]

#->CR[#]&/@ CographLayout[5]

Permutations

t1[1]:=2;t1[2]:=1;t1[n_]:=n

Endograph[t1,5]

t2[1]:=2;t2[2]:=4;t2[4]:=1;t2[3]:=0;t2[0]:=3;t2[n_]:=n

Cograph[t1,5]

Endograph[t2,5]

Cograph[t2,5]

GraphPlot[CographFunctionRule[t2,5],VertexLabeling->True,DirectedEdges->True,EdgeRenderingFunction->(Arrow[#1,0.1]&),PlotStyle->Directive[Arrowheads[0.04]],VertexCoordinateRules->{0->{0,2},1->{2,2},2->{3,2},3->{1,2},4->{4,2},100->{0,0},101->{2,0},102->{3,0},103->{1,0},104->{4,0}},VertexRenderingFunction->(Text[Lab[#2],#1]&),ImageSize->Small]

DFGraph[t2,5]

Tree Structure

f3[n_]:=Mod[2n^9+5n^8+n^7+4n^6+9n^5+1,11]

2n^9+5n^8+n^7+4n^6+9n^5+1//TeXForm

Endograph[f3,11]

CographFunctionRule[f3,11]

Cograph[f3,11]

f4[n_]:=Mod[2n^9+5n^8+n^7+4n^6+9n^5+6,11]

Endograph[f4,11]

f5[n_]:=Mod[2n^9+2n^8+n^7+4n^6+n^5+n^3+6n^2+6,11]

Endograph[f5,11]

ru1:={1->2,2->3,3->4,4->1,5->2,6->2,7->6,8->6,9->4,10->9,11->9,12->11,0->11,13->3,14->4,15->4,16->15}

RuleGraph[ru1]

Involutions

ru2:={1->2,2->1,3->3,4->4,5->6,6->5}

RuleGraph[ru2]

ru3:={1->1,2->2,3->3,4->4,5->2,6->2,7->6,8->6,9->4,10->9,11->9,12->11,0->11,13->3,14->4,15->4,16->15}

RuleGraph[ru3]

f7[x_]:=x/.ru3

Table[{x,f7[x]},{x,0,16}]

Table[{x,f7[f7[x]]},{x,0,16}]

Idempotents

ru4:={1->1,2->2,3->3,4->4,5->4,6->4,7->3,8->2,9->1,10->1,11->1,12->2,13->2,14->2,15->3,16->3}

RuleGraph[ru4]

f8[x_]:=x/.ru4

Table[{x,f8[x],f8[f8[x]]},{x,0,16}]//tf

Old Examples

Example 1

ru1:={a->a,c->d,b->c,d->a,e->d,f->e,g->b,h->d,i->h,j->e}

ru1

RuleGraph[ru1]

LGraph[ru1]

Example 2

g[n_]:=Mod[n^2+1,13]

MakeFunctionRule[g,13]
{0->1,1->2,2->5,3->10,4->4,5->0,6->11,7->11,8->0,9->4,10->10,11->5,12->2}

Endograph[g,13]

DFGraph[g,13]

h[n_]:=Mod[n^9,11]

Example 3

MakeFunctionRule[h,11]
{0->0,1->1,2->6,3->4,4->3,5->9,6->2,7->8,8->7,9->5,10->10}

RuleGraph[MakeFunctionRule[h,11]]

DFGraph[h,11]

Example 4

k[n_]:=Mod[n^9+n^7+5n,11]

Endograph[k,11]

DFGraph[k,11]

Example 5

s[n_]:=Mod[(n+1)^9+n^7+5n,11]

Endograph[s,11]

DFGraph[s,11]

aaa[n_]:=Mod[(n+1)^9+(n^+2)^7+5n,11]

Endograph[aaa,11]

DFGraph[aaa,11]

bbb[n_]:=Mod[n^2+5,11]

Endograph[bbb,11]

DFGraph[bbb,11]

ccc[n_]:=Mod[n^3+5,11]

Endograph[ccc,11]

DFGraph[ccc,11]

x[n_]:=bbb[ccc[n]]

{DFGraph[ccc,11], DFGraph[bbb,11], DFGraph[x,11]}

ddd[n_]:=Mod[n^3+n^2,11]

Endograph[ddd,11]

DFGraph[ddd,11]

p[n_]:=Mod[n^2+1,11]

Endograph[p,11]

DFGraph[p,11]

pp[x_]:=p[p[x]]

Endograph[pp,11]

DFGraph[pp,11]

ppp[x_]:=p[p[p[x]]]

Endograph[ppp,11]

DFGraph[ppp,11]

dddOp[n_]:=ddd[p[n]]

DFGraph[dddOp,11]

pOddd[n_]:=p[ddd[n]]

{DFGraph[p,11], DFGraph[ddd,11], DFGraph[dddOp,11], DFGraph[pOddd,11]}

ht[n_]:=Mod[n^(11),13]

Endograph[ht,13]

DFGraph[ht,11]

htx[n_]:=Mod[n^(11)+n^9+n^7+1,13]

htx[11]

Endograph[htx,13]

DFGraph[htx,11]

Table[{n,htx[n]},{n,0,12}]//tf
({{0, 1}, {1, 4}, {2, 11}, {3, 1}, {4, 1}, {5, 9}, {6, 11}, {7, 4}, {8, 6}, {9, 1}, {10, 1}, {11, 4}, {12, 11}})

fbig[0]:=5;fbig[1]:=2;fbig[2]:=13;fbig[3]:=4;fbig[4]=14;fbig[5]:=6;fbig[6]:=7;fbig[7]:=8;fbig[8]:=9;fbig[9]:=10;fbig[10]:=5;fbig[11]:=2;fbig[12]:=2;fbig[13]:=14;fbig[14]:=7;

Endograph[fbig,15]

DFGraph[fbig,11]

uuu[n_]:=Mod[n^5+1,11];vvv[n_]:=Mod[n^6+1,11]; www[n_]:=uuu[vvv[n]];xxx[n_]:=vvv[uuu[n]]

{DFGraph[uuu,11], DFGraph[vvv,11], DFGraph[www,11], DFGraph[xxx,11]}

uuu[n_]:=Mod[n^5,11];vvv[n_]:=Mod[n^6,11]; www[n_]:=uuu[vvv[n]];xxx[n_]:=vvv[uuu[n]]

{DFGraph[uuu,11], DFGraph[vvv,11], DFGraph[www,11], DFGraph[xxx,11]}

Experiment: Why don’t this version of VertexCoordinateRules work?

GraphPlot[{{0,2}->{3,0},{1,2}->{2,0},{2,2}->{4,0},{3,2}->{0,0},{4,2}->{1,0}},VertexLabeling->True,DirectedEdges->True,EdgeRenderingFunction->(Arrow[#1,0.1]&),PlotStyle->Directive[Arrowheads[0.04]],VertexCoordinateRules->{{0,0}->{0,0},{0,2}->{0,2},{1,0}->{1,0},{1,2}->{1,2},{2,0}->{2,0},{2,2}->{2,2},{3,0}->{3,0},{3,2}->{3,2},{4,0}->{4,0},{4,2}->{4,2}},VertexRenderingFunction->(Text[#2[[1]],#1]&),ImageSize->Small]

Polynomials over finite fields

ru1:={1->2,2->3,3->4,4->1,5->2,6->2,7->6,8->6,9->4,10->9,11->9,12->11,0->11,13->3,14->4,15->4,16->15}

gr:={#,#/.ru1}&/@Table[n,{n,0,16}]

gr

t4[x_]:=PolynomialMod[InterpolatingPolynomial[gr,x,Modulus->17]//Expand,17]

t4[x]

t4[x]//tx

Endograph[t4,17]

RuleGraph[ru1]