Skip to content

Latest commit

 

History

History
234 lines (159 loc) · 6.49 KB

PITCHME.md

File metadata and controls

234 lines (159 loc) · 6.49 KB

A poly-time test for difference terms in idempotent varieties

William DeMeo <[email protected]>

joint work with Ralph Freese & Matt Valeriote

BLAST 2017 @ Vanderbilt

The Problem

Can we efficiently decide whether a finite algebra $\mathbf{A}$ generates a variety with a difference term?

We will outline the proof that the answer is "yes" in the idempotent case.

Definition

A difference term for $\mathcal{V}$ is a term $d$ satisfying, $\forall ; \mathbf A \in \mathcal V$ and $\forall a, b \in A$,

$$d(a,a,b) = b \quad \text{ and } \quad d(a,b,b) \mathrel{[\theta, \theta]} a$$

where $\theta$ is any congruence containing $(a,b)$ and $[\cdot, \cdot]$ is the commutator.

Problem Statement

Is there a poly-time algorithm that takes a finite idempotent algebra $\mathbf{A}$ and decides whether $\mathbb{V}(\mathbf{A})$ has a difference term?

**Theorem** (Kearnes, *J Algebra* 1995) $\mathbb{V}(\mathbf{A})$ has a difference term $\; \Longleftrightarrow \;$ $\mathbb{V}(\mathbf{A})$ omits type 1 and type-2 tails

Omitting 1 is poly-time decidable by Valeriote's subtype theorem.

**Reduced Problem** Is there a poly-time algorithm that takes a finite idempotent algebra $\mathbf{A}$ and decides whether $\mathbb{V}(\mathbf{A})$ has nonempty type-2 tails?

Strategy

*Kearnes:* Having a diff term is characterized by omitting 1's and type-2 tails.

*Valeriote:* Omitting 1's is poly-time decidable by the subtype theorem.

*To show:* Type-2 tails, when they occur in $\mathbb{V}(\mathbf{A})$, are easy to find.

---?image=http://www.propinsanity.com/wp-content/uploads/2014/09/image.jpg

Main Theorem

Let $\mathbf A$ be a finite idempotent algebra.

Suppose $\mathbb{V}(\mathbf A)$ omits type 1 and contains a finite algebra $\mathbf{B}$ with a type-2 prime quotient $\alpha \prec \beta$ such that the $\langle \alpha, \beta \rangle$-minimal sets have nonempty tails.

Then there exists a 3-generated subalgebra of $\mathbf A \times \mathbf A$ with this property.

**Conclusion:** to check for type-2 tails in $\mathbb{V}(\mathbf A)$ it suffices to look in 3-generated subalgebras of $\mathbf A \times \mathbf A$.

Notation

$[n] = { 0, 1, \dots, n-1 }, \qquad \rho_i = \operatorname{ker} (\mathbf B \twoheadrightarrow \mathbf A_i), \qquad \rho_s = \bigwedge_s \rho_j$

Let $S$ be a finite set of finite idempotent algebras that is closed under taking subalgebras.

Assume $\mathbb{V}(S)$ omits type 1.

Suppose there is a finite $\mathbf{B} \in \mathbb{V}(S)$ with type-2 tails.

WLOG Assume $\mathbf B$ is a subdirect product of a finite number of members of $S$.

Choose $n$ minimal such that for some $\mathbf{A}_1$, $\mathbf{A}_2$, $\dots$, $\mathbf{A}_n$ in $S$,

$$\mathbf{B} \leq_s \prod \mathbf{A}_i$$

Under the assumption that $n &gt; 1$ we will prove $n = 2$.

Minimality Assumptions

For this $n$, select the $\mathbf{A}_i$ and $\mathbf{B}$ so that $|B|$ is as small as possible.

Let $\alpha \prec \beta$ be a type-2 prime quotient of $\mathbf B$ whose minimal sets have nonempty tails, and choose $\beta$ minimal with respect to this property.

This implies $\beta$ is join irreducible and $\alpha$ is its unique subcover (HM Lemma 6.2).

Fourfold Path to a Proof

Lemma 1
Suppose $U$ is an $\langle \alpha, \beta \rangle$-minimal set and $0, 1 \in U$ and $(0,1) \in \beta - \alpha$ and $t \in Tail(U)$

Then $\beta = \operatorname{Cg}(0,1)$ and $\mathbf B$ is generated by ${0, 1, t}$.

**Lemma 2** For every $s \subset [n]$, either $\beta \leq \rho_s$ or $\alpha \vee \rho_s = 1_B$.

**Lemma 3** $\forall \; s \subset [n], \quad \forall \; v\in B, \quad \forall \; b\in Body(U), \qquad (v,b) \in \beta \circ \rho_s \cap \rho_s \circ \beta$.

**Lemma 4** There exist $i$ and $j$ such that $\alpha \vee \rho_i = 1_B$ and $\alpha \vee \rho_j &lt; 1_B$.

Theorem

Let $\mathcal V$ be the variety generated by a finite set $\mathcal S$ of finite idempotent algebras that is closed under taking subalgebras.

Suppose $\mathcal V$ omits 1 and some finite member of $\mathcal V$ has a prime quotient of type 2 whose minimal sets have non-empty tails.

Then there is some 3-generated algebra with this property that belongs to $\mathcal S$ or is a subdirect product of two algebras from $\mathcal S$.

Proof

By Lemma 1, $\mathbf B$ is 3-generated.

If $n &gt; 1$ then Lemmas 2 and 4 imply $\exists$ $i, j$ such that $\beta \leq \rho_i$ and $\alpha \vee \rho_j = 1_B$.

If $n &gt; 2$ then Lemma 2 applies to $\rho = \rho_i \wedge \rho_j$, so either (1) $\beta \leq \rho$ or (2) $\alpha \vee \rho = 1_B$.

(1) impossible, since $\beta \not\le \rho_j$ (2) impossible, since both $\alpha$ and $\rho$ are below $\rho_i$.

So, $n\leq 2$ and the theorem is proved.

Future Work

Questions

Is there a poly-time algorithm for producing a difference term when such a term is known to exist?

Conjectures

This new test for existence of a difference term will soon appear in the *Idempotent* menu of UACalc.

Thank you!