Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

We are talking about algebras in the universal algebraic sense, that is, a set that $A$ is equipped with a set $F$ of finitary operations on $A$.

Definition: An algebra $(A,F)$ is said to have finite essential arity if there exists a number $n \in \mathbb{N}$ such that each of its term functions depends on at most $n$ variables.

I am mostly interested in the case where $A$ is finite. I have read some results about this, but I am not sure what exactly is known about these kind of algebras.

I am particularly interested in identities that hold (or don't hold) for algebras of this kind. I know a few conditions on identities that imply finite essential arity, but not so many that are required or even equivalent. Thus, I would be very interested in examples of this kind.

To ask one more specific question that goes in the same direction: Are there (finite) algebras with finite essential arity that are not strongly abelian? What would be an example for that?

share|improve this question

2 Answers 2

Summary

There are semigroups of finite essentially arity which are not strongly abelian. This follows from my original answer and a result I cite in the addition below that I have not read in detail.

Added. Here is a self-contained answer. Take the semigroup $S=\langle x\mid x^3=x^4\rangle$. Then consider the term $t(x_1,x_2)=x_1x_2$. One has $t(x,x^3)=x^3=t(x^2,x^3)$ but $t(x,x)=x^2\neq x^3=t(x^2,x)$. So $S$ is not strongly abelian. But the essential arity of $S$ is $3$ since the value of any word of length $\geq 3$ in $S$ is $x^3$.


Original Answer

A finite semigroup $S$ has finite essential arity iff it is locally trivial, that is, $eSe=e$ for all idempotents $e\in S$.

Pf. First suppose that $S$ is not locally trivial. The either $S$ contains a subsemigroup isomorphic to the 2-element semilattice $\lbrace 0,1\rbrace$ with multiplication or it contains a non-trivial group $G$ as a subsemigroup.

In the first case, the variety generated by $S$ contains the free semilattice on any set (i.e. the power set under union with singletons as free generators) and so the term function given by a word on m-letters depends on all those letters. If $S$ contains a non-trivial group $G$, then it contains a cyclic group of prime order $p$ and hence vector spaces over $\mathbb F_p$. But then again the term function depending on any word in m-letters depends on all letters by considering a vector space of dimension m.

So finite essential arity implies locally trivial.

Conversely, if $S$ is locally trivial, then it is known that $S$ satisfies an identity of the form $$x_1\cdots x_myz_1\cdots z_n = x_1\cdots x_mz_1\cdots z_n$$ and so any term operation coming from a word depends only on at most $m+n$ variables (the prefix of length $m$ and the suffix of length $n$).

In particular, no non-trivial monoid has finite essential arity.


Added. If I understood correctly the results of Stepanova, A. A.(RS-FARE-IMC); Trikashnaya, N. V.(RS-FARE-IMC) Abelian and Hamiltonian varieties of groupoids, Algebra Logic 50 (2011), no. 3, 272–278 then a locally trivial semigroup is strongly abelian iff it is an inflation of a rectangular band. Most locally trivial semigroups are not inflations of a rectangular band. If $S$ is an inflation of a rectangular band, then $S^2=S^3$. But if one takes the semigroup $\langle x\mid x^3=x^4\rangle$, then it is locally trivial (hence essentially finite arity) but it is not strongly abelian.

share|improve this answer
    
Thanks a lot for the answer, which seems to be very intersting. At this point, I don't know much more to say since I am not at all familiar with the result you cite. I will get back to you on this. –  Niemi Apr 25 '13 at 9:04
    
I gave now a self-contained proof that the three-element nilpotent cyclic semigroup has essential arity 3 but is not strongly abelian. Every 2-element semigroup of finite essential arity is strongly abelian so this example is minimal. –  Benjamin Steinberg Apr 25 '13 at 13:46
    
By the way the free semigroup belongs to the variety generated by all finite semigroups of finite essential arity so you cannot in some sense describe this property by satisfiability of usual identities. But locally trivial semigroups form a pseudovariety and can be defined by a single pseudoidentity. –  Benjamin Steinberg Apr 25 '13 at 13:53

I define a kind of template or macro to be used in a slightly odd fashion, not exactly typed second order logic. Let Ab(t,A,B) be the macro that expands (when appropriate inputs are given) to the logical expression (t(A,xbar) = t(A,ybar)) implies (t(B,xbar) = t(B,ybar)) . Similarly for SAb(t,B,C,D), using (t(C,xbar)=t(D,ybar)) implies (t(B,xbar)=t(B,ybar)). Now for a given algebra AA, ((for any xbar and ybar which are tuples of appropriate length built from (the underlying set of) AA, for any term t from (the set of term operations of) AA, [For any a,b from AA Ab(t,a,b) holds] )) iff AA is abelian.

Replacing the "last line" in the above with [For any b,c,d from AA Sab(t,b,c,d) holds] )) iff AA is strongly abelian gets the definition of a strongly abelian algebra as well.

There are variants of the above defintions where binary terms t(a,x) instead of larger arity terms t(a,xbar) are used, and for two congruences $\alpha \leq \beta$ of AA one can define a generalization ($\beta$ is abelian or strongly abelian over $\alpha$) using $\alpha$-related in place of = and asking for certain of a,b,c,d and the bars to be $\beta$-related. Also, once the defintion is understood for an algebra AA, it can be extended to apply to classes of algebras.

A web search for strongly abelian universal algebra leads to various papers in the literature, with Kiss, McKenzie, and Valeriote among the authors. Kiss and Valeriote in a paper on Abelian Algebras and the Hamiltonian Property mention some of the literature and note that matrix powers of unary algebras provide basic examples of strongly Abelian algebras. In another paper on strongly abelian varieties these same two authors mention the result that strongly abelian algebras have finite essential arity, and that something similar holds for locally finite strongly abelian varieties.

I know of no nice way of expressing essential arity in terms of identities. The not so nice way involves picking an integer n and then a certain set of formulas which are tantamount to saying t(abar,xbar)=t(abar,ybar), except one needs to single out the inessential variables where they live rather than conveniently grouping them together into xbar or ybar.

I have no specific example of an algebra that is not strongly abelian, but is of bounded essential arity. Here is an idea on how to build one though a finite such algebra. Take a universe of size n at least 4. (Smaller might work, but I want enough room for success.) Order the set as a chain, with 0 as the least. Create an operation of desired arity and call it b and make sure it is not strongly abelian by ensuring that b(a,xbar) is different from b(a,ybar) for at least one valuation of a, xbar,and ybar, while making it agree for c,xbar and d,ybar.

Compatible with that condition, let b have the value v satisfy that it is smaller than any of the values of its arguments, unless one of them is 0 in which case 0=b(a,ybar). Now any term which has a depth of n many b's will evaluate to 0, and be constant. If you take sufficient care, you can show that this algebra has essential arity at most w^n for w the essential arity of b.

Gerhard "Ask Me About System Design" Paseman, 2013.04.24

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.