cycred: Cyclic reductions of a word

In RobinHankin/freegroup: The Free Group

Cyclic reductions of a word

Description

Functionality to cyclically reduce words and detect conjugacy

Usage

is.cyclically_reduced(a)
as.cyclically_reduced(a)
cyclically_reduce(a)
cyclically_reduce_tietze(p)
is.conjugate_single(u,v)
x %~% y
## S3 method for class 'free'
is.conjugate(x,y)
allconj(x)

Arguments

a,x,y	An object of class free
p,u,v	Integer vector corresponding to Tietze form of a word

Details

A free object is cyclically reduced iff every cyclic permutation of the word is reduced. A reduced word is cyclically reduced iff the first letter is not the inverse of the last one. A reduced word is cyclically reduced if the first and last symbol differ (irrespective of power) or, if identical, have powers of opposite sign. For example, abac and abca are cyclically reduced but abca^{-1} is not. Function is.cyclically_reduced() tests for this.

Function as.cyclically_reduced() takes a vector of free objects and returns the elementwise cyclically reduced equivalents. Function cyclically_reduce() is a synonym with better (English) grammar.

The identity is cyclically reduced: it cannot be shortened by a combination of cyclic permutation followed by reduction. This ensures that is.cyclically_reduced(as.cyclically_reduced(x)) is always TRUE. Also, it is clear that the identity should be conjugate to itself.

Two words a,b are conjugate if there exists a x such that ax=xb (or equivalently a=x^{-1}bx). This is detected by function is.conjugate(). Functions is_conjugate_single() and cyclically_reduce_tietze() are lower-level helper functions.

Function allconj() returns all cyclically reduced words conjugate to its argument.

Author(s)

Robin K. S. Hankin

See Also

reduce

Examples

(x <- abc(1:9) - abc(9:1))
as.cyclically_reduced(x)

 a <- rfree(1000,3)
 all(size(as.cyclically_reduced(a)) <= size(a))
 all(total(as.cyclically_reduced(a)) <= total(a))
 all(number(as.cyclically_reduced(a)) <= number(a))



 x <- rfree(1000,2)
 y <- as.free('ab')
 table(conjugate = (x%~%y), equal = (x==y))  # note zero at top right

 allconj(as.free('aaaaab'))
 allconj(sum(abc(seq_len(3))))



 x <- rfree(1,10,8,8)
 all(is.id(allconj(x) + allconj(-x)[shift(rev(seq_len(total(x))))]))

RobinHankin/freegroup documentation built on March 11, 2024, 12:32 a.m.