text:
section \<open>Bounded Degree Polynomials\<close>

text \<open>This section contains a definition for the set of polynomials with a degree bound and
establishes its cardinality.\<close>

theory Bounded_Degree_Polynomials
  imports "HOL-Algebra.Polynomial_Divisibility"
begin

lemma (in ring) coeff_in_carrier: "p \<in> carrier (poly_ring R) \<Longrightarrow> coeff p i \<in> carrier R"
  using poly_coeff_in_carrier carrier_is_subring  by (simp add: univ_poly_carrier)

definition bounded_degree_polynomials
  where "bounded_degree_polynomials F n = {x. x \<in> carrier (poly_ring F) \<and> (degree x < n \<or> x = [])}"

text \<open>Note: The definition for @{term "bounded_degree_polynomials"} includes the zero polynomial
in @{term "bounded_degree_polynomials F 0"}. The reason for this adjustment is that, contrary to
definition in HOL Algebra, most authors set the degree of the zero polynomial to
$-\infty$~\cite[\textsection 7.2.2]{shoup2009computational}. That
definition make some identities, such as $\mathrm{deg}(f g) = \mathrm{deg}\, f + \mathrm{deg}\, g$
for polynomials $f$ and $g$ unconditionally true.
In particular, it prevents an unnecessary corner case in the statement of the results established
in this entry.\<close>

lemma bounded_degree_polynomials_length:
  "bounded_degree_polynomials F n = {x. x \<in> carrier (poly_ring F) \<and> length x \<le> n}"
  apply (simp add:bounded_degree_polynomials_def)
  apply (rule Collect_cong)
  by (metis Suc_pred length_greater_0_conv less_Suc_eq_0_disj less_Suc_eq_le linorder_not_le)

lemma (in ring) fin_degree_bounded:
  assumes "finite (carrier R)"
  shows "finite (bounded_degree_polynomials R n)"
proof -
  have "bounded_degree_polynomials R n \<subseteq> {p. set p \<subseteq> carrier R \<and> length p \<le> n}"
    apply (rule subsetI)
    apply (simp add: bounded_degree_polynomials_length) using assms(1)
    by (meson polynomial_incl univ_poly_carrier)
  thus ?thesis  apply (rule finite_subset)
    using assms(1) finite_lists_length_le by auto
qed

lemma (in ring) non_empty_bounded_degree_polynomials:
  "bounded_degree_polynomials R k \<noteq> {}"
proof -
  have "\<zero>\<^bsub>poly_ring R\<^esub> \<in> bounded_degree_polynomials R k"
    by (simp add: bounded_degree_polynomials_def univ_poly_zero univ_poly_zero_closed)
  thus ?thesis by auto
qed

lemma in_image_by_witness:
  assumes "\<And>x. x \<in> A \<Longrightarrow> g x \<in> B \<and> f (g x) = x"
  shows "A \<subseteq> f ` B"
  by (metis assms image_eqI subsetI)

lemma card_mostly_constant_maps:
  assumes "y \<in> B"
  shows "card {f. range f \<subseteq> B \<and> (\<forall>x. x \<ge> n \<longrightarrow> f x = y)} = card B ^ n" (is "card ?A = ?B")
proof -
  define f where "f = (\<lambda>f k. if k < n then f k else y)"

  have "card ?A = card (f ` ({0..<n}  \<rightarrow>\<^sub>E B))"
    apply (rule arg_cong[where f="card"])
    apply (rule order_antisym) (* TODO Split *)
     apply (rule in_image_by_witness[where g="\<lambda>f. restrict f {0..<n}"])
     apply (rule conjI, simp add: range_subsetD)
     apply (rule ext, simp add:restrict_def Pi_def PiE_def f_def)
    apply (rule image_subsetI, simp add:f_def)
    apply (rule conjI)
     apply (metis Int_iff PiE PiE_def atLeastLessThan_iff image_Collect_subsetI less_eq_nat.simps(1))
    by (rule image_subsetI, rule assms)
  also have "... = card ({0..<n} \<rightarrow>\<^sub>E B)"
    apply (rule card_image, rule inj_onI, rule ext, simp add:f_def)
    by (metis PiE_arb atLeastLessThan_iff)
  also have "... = card B ^ n"
    by (subst card_PiE, simp, simp)
  finally show ?thesis by simp
qed

definition (in ring) build_poly where
  "build_poly f n = normalize (rev (map f [0..<n]))"

lemma (in ring) poly_degree_bound_from_coeff:
  assumes "x \<in> carrier (poly_ring R)"
  assumes "\<And>k. k \<ge> n \<Longrightarrow> coeff x k = \<zero>"
  shows "degree x < n \<or> x = \<zero>\<^bsub>poly_ring R\<^esub>"
proof (rule ccontr)
  assume a:"\<not>(degree x < n \<or> x = \<zero>\<^bsub>poly_ring R\<^esub>)"
  hence b:"lead_coeff x \<noteq> \<zero>\<^bsub>R\<^esub>"
    by (metis assms(1) polynomial_def univ_poly_carrier univ_poly_zero)
  hence "coeff x (degree x) \<noteq> \<zero>"
    by (metis a lead_coeff_simp univ_poly_zero)
  moreover have "degree x \<ge> n" by (meson a not_le)
  ultimately show "False" using assms(2) by blast
qed

lemma (in ring) poly_degree_bound_from_coeff_1:
  assumes "x \<in> carrier (poly_ring R)"
  assumes "\<And>k. k \<ge> n \<Longrightarrow> coeff x k = \<zero>"
  shows "x \<in> bounded_degree_polynomials R n"
  using poly_degree_bound_from_coeff[OF assms]
  by (simp add:bounded_degree_polynomials_def univ_poly_zero assms)

lemma (in ring)
  assumes "\<And>i. i < n \<Longrightarrow> f i \<in> carrier R"
  shows
    build_poly_poly: "build_poly f n \<in> carrier (poly_ring R)" and
    build_poly_coeff: "\<And>i. coeff (build_poly f n) i = (if i < n then f i else \<zero>)" and
    build_poly_degree: "degree (build_poly f n) \<le> n - 1"
proof -
  show a:"build_poly f n \<in> carrier (poly_ring R)"
    apply (simp add:build_poly_def univ_poly_carrier[symmetric])
    apply (rule normalize_gives_polynomial, simp)
    using assms atLeastLessThan_iff by blast

  show b:"\<And>i. coeff (build_poly f n) i = (if i < n then f i else \<zero>)"
  proof -
    fix i :: nat
    show "coeff (build_poly f n) i = (if i < n then f i else \<zero>)"
      apply (cases "i < n")
      apply (simp add:build_poly_def normalize_coeff[symmetric])
       apply (subst coeff_nth, simp, simp add:rev_nth)
      apply (simp add:build_poly_def normalize_coeff[symmetric])
      by (subst coeff_length, simp, simp)
  qed

  have "degree (build_poly f n) < n \<or> build_poly f n = \<zero>\<^bsub>poly_ring R\<^esub>"
    apply (rule poly_degree_bound_from_coeff[OF a])
    using b by simp

  thus "degree (build_poly f n) \<le> n - 1"
    apply (cases n, simp add:build_poly_def)
    by (metis diff_Suc_1 diff_is_0_eq less_Suc_eq_le list.size(3) univ_poly_zero zero_diff)
qed

lemma (in ring) length_build_poly:
  "length (build_poly f n) \<le> n"
  apply (simp add:build_poly_def)
  by (metis length_map normalize_length_le length_rev length_upt less_imp_diff_less linorder_not_less)

text \<open>The following establishes the total number of polynomials with a degree less than $n$.
Unlike the results in the following sections, it is already possible to establish this property for
polynomials with coefficients in a ring.\<close>

lemma (in ring) bounded_degree_polynomials_card:
  "card (bounded_degree_polynomials R n) = card (carrier R) ^ n"
proof -
  have a:"coeff ` bounded_degree_polynomials R n \<subseteq> {f. range f \<subseteq> (carrier R) \<and> (\<forall>k \<ge> n. f k = \<zero>)}"
    apply (rule image_subsetI, simp add:bounded_degree_polynomials_def, rule conjI)
    using coeff_length coeff_in_carrier by auto

  have b:"{f. range f \<subseteq> (carrier R) \<and> (\<forall>k \<ge> n. f k = \<zero>)} \<subseteq> coeff ` bounded_degree_polynomials R n"
    apply (rule in_image_by_witness[where g="\<lambda>x. build_poly x n"])
    apply (rule conjI, rule poly_degree_bound_from_coeff_1)
      apply (rule build_poly_poly, blast)
     apply (subst coeff_length, metis length_build_poly order_trans, simp)
    by (rule ext, subst build_poly_coeff, blast, simp)

  have "card ( bounded_degree_polynomials R n) = card (coeff `  bounded_degree_polynomials R n)"
    apply (rule card_image[symmetric])
    apply (rule inj_on_subset[where A="carrier (poly_ring R)"])
     apply (rule inj_onI, simp add: coeff_iff_polynomial_cond univ_poly_carrier)
    by (simp add:bounded_degree_polynomials_def)
  also have "... = card {f. range f \<subseteq> (carrier R) \<and> (\<forall>k \<ge> n. f k = \<zero>)}"
    by (rule arg_cong[where f="card"], rule order_antisym[OF a b])
  also have "... = card (carrier R)^n"
    by (rule card_mostly_constant_maps, simp)
  finally show ?thesis by simp
qed

end

subset_name: curated


TITLE: subgroups of regular polytopes that preserve a given face
QUESTION [2 upvotes]: Say I have a regular polytope (e.g. it is vertex and face transitive). Given a face F, is it true that there are symmetry operations taking every vertex of F to every other that also send F to its self? I know that every face of a regular polytope is a regular polytope, so this seems like a logical assertion.
To give an example of where this holds, for a face of a cube there is a cyclic subgroup that permutes all vertices of any of given square face, whilst mapping that face to its self (e.g. the rotations about the normal of that face)

REPLY [0 votes]: Yes. The more general definition of a regular polytope is that its symmetry group acts transitively on its flags. A flag is a maximal chain of incident faces, e.g. for a polyhedron, a vertex $v$, an edge $e$ containing $v$, and a face containing $e$.
So, with a regular polyhedron, you can pick a vertex $v$, a face $f$, and an edge $e$ of $f$ containing $v$, and map it to the same face $f$, any vertex $w$ of $f$, and either of the edges $e'$ of $f$ containing $w$.


TITLE: Listing all posets on 9 points?
QUESTION [10 upvotes]: I'm looking for a list of all (non-isomorphic) posets on 9 points. I know there are 183231 of them (OEIS A000112), but in order to progress with a problem I'm working on, I'd need the posets themselves, not only their number.
Background: A poset is a set $S$ together with a relation $\le$ on $S$ which is reflexive, transitive, and antisymmetric.  Elements of $S$ are called points here.  Two posets are isomorphic if there is a relation-respecting bijection between them.  Deciding whether two posets are isomorphic is known to be a difficult problem, and the numbers of isomorphism classes of finite posets are known only for posets with up to 16 points (see the OEIS entry cited above).  State of the art is a 2002 paper by Brinkmann and McKay: "Posets on up to 16 Points", Order 19 (2) (2002) 147-179.

REPLY [2 votes]: The following file lists adjacency matrices of all 183231 inequivalent partial orders (i.e., $T_0$ topologies) on 9 points, with spaces separating rows:
https://www.mathtransit.com/finite_topological_spaces/9-spaces_T_0_binary.txt.gz
I created this file from one that was at the now-defunct Chapel Hill Poset Atlas, the front page of which can still be viewed here:
http://web.archive.org/web/20190905161049/https://lists-of-posets.math.unc.edu/
In late 2019 I posted files containing all nonhomeomorphic topologies on spaces up to and including 9 points, here:
https://www.mathtransit.com/finite_topological_spaces.php
I am currently in the process of expanding this page to include files for cardinalities 10 and 11, the latter of which will probably take the form of a simple cookbook recipe due to its large size.


TITLE: Why isn't sunset time in sync with solstice?
QUESTION [5 upvotes]: The winter solstice in the Northern Hemisphere in 2011 is on December 22.
But if I look at the sunset times for a location such as Washington, DC on the USNO site, the sunset time starts reversing much earlier (around December 6th).
Shouldn't the sunset time start reversing (from earlier to later) on the same date as the solstice?
Update:
Omega Centauri's explanation is correct.

The Royal Observatory gives a similar account of this oddity on this page under the section titled "The apparently odd behaviour of sunrise/set times near the winter solstice".
Cornell University provides more details here.

REPLY [3 votes]: This is because the earth doesn't have a circular orbit, so some times the angular velocity of the earth is greater than average (and also the reverse). Perihelion is in early January, so the planets orbital velocity is greater (i.e. the Northern hemisphere winter is shorter than half a year long). So the affects the length of a day, making it differer slightly from 24hours depending upon the season. So solar time versus clock times drifts.


TITLE: Does $f_n\rightarrow f$ uniformly suggest $\sum f_n\rightarrow\sum f$ uniformly?
QUESTION [2 upvotes]: Let $\{f_n\}$ be a sequence of functions that converge uniformly to
  $f$ in $(0,1]$. For every sequence $\{x_n\}$ such that
  $x_n\rightarrow0^+$, the series $\sum_{n=1}^\infty f(x_n)$ diverges.
  Show that $\sum f_n(x_n)$ also diverges for every sequence
  $x_n\rightarrow0^+$.

My try-
By negation, we assume there exists a sequence $\{y_n\}$, such that $y_n\rightarrow 0^+$ and $\sum f_n(y_n)$ converges to a function $S(y_n)$.
I want to show that $\sum f(y_n)$ also converges, yielding a contradiction.
So we have
$|\sum f(y_n)-S(y_n)|\leq|\sum f_n(y_n)-\sum f(y_n)|+|\sum f_n(y_n)-S(y_n)|$
$|\sum f_n(y_n)-S(y_n)|$ is as small as we want because of the convergence, and I know $|f_n(y_n)-f(y_n)|$ is as small as we want thanks to uniform convergence.
But what about $|\sum f_n(y_n)-\sum f(y_n)|$?
Does $f_n\rightarrow f$ uniformly suggest $\sum f_n\rightarrow\sum f$ uniformly?

REPLY [1 votes]: Let $L = \liminf_{x\to 0^+} |f(x)|.$ If $L = 0,$ then there is a sequence $x_n \to 0^+$ such that $|f(x_k)| \to 0.$ This implies there is a subsequence $n_k$ such that $|f(x_{n_k})|\le 1/2^k.$ Hence the series $\sum f(x_{n_k})$ converges absolutely. This is a contradiction since $x_{n_k} \to 0^+.$
So we know $L>0.$ Thus there is $b>0$ such that $|f(x)| > L/2$ for $x\in (0,b).$ To finish, use the uniform convergence of $f_n$ to $f$ to show there exists $N$ such that for all $n\ge N,$ $|f_n(x)|> L/4$ for all $x\in (0,b).$ This leads to the desired conclusion.


TITLE: Power series expansion of $\arctan (x)$ centered at $x=0$ extends to $x=1$?
QUESTION [1 upvotes]: In my real analysis class (this is a HW question) I have been given the following problem:

Show that $\dfrac{1}{1 + x^2} = \sum_{n=0}^{\infty} (-1)^n x^{2 n}$ when $|x|<1$.
Show that $\arctan (x)=\sum_{n=0}^{\infty} \dfrac{(-1)^n x^{2n + 1}}{2n + 1}$ when $|x|<1$.
Show that series for $\arctan (x)$ in the previous part also holds when $x=1$.

Here is my work for parts 1 & 2.
Since $|x^2| < 1$ as $|x| < 1$, we have that
\begin{align*}
                \dfrac{1}{1+x^2}&= \dfrac{1}{1-(-x^2)}\\
                &=\sum_{n=0}^\infty \left(-x^2\right)^n\\
                &=\sum_{n=0}^\infty (-1)^n x^{2n}
            \end{align*}
whenever $|x| < 1$.
We know that $\dfrac{d}{dx}\arctan (x) =\dfrac{1}{1+x^2}$, and thus, we may integrate termwise on the power series expansion of $\dfrac{1}{1+x^2}$ which we have already found:
\begin{align*}
                \arctan(x)&= \int \sum_{n=0}^\infty (-1)^n x^{2n} dx\\
                &= \sum_{n=0}^\infty \int (-1)^n x^{2n} dx\\
                &= \sum_{n=0}^\infty \dfrac{(-1)^nx^{2n+1}}{2n+1}.
            \end{align*}
I am unsure how to proceed with part $3$. I found it peculiar how this question and this question both use complex analysis to solve it, which I'm sure is not what my professor intends (we have done nothing with complex numbers in this course). If I had to guess, we are intended to use Abel's theorem, but I don't see how this question meets all the necessary requirements of Abel's Theorem.  I'm looking for intuition on how to use the theorem. Thanks!

REPLY [1 votes]: This is famously known as the Leibniz $\pi$ formula. https://en.wikipedia.org/wiki/Leibniz_formula_for_%CF%80 has a neat proof without using any fancy series tools. Using the form of Abel's theorem stated here: Proof of Leibniz $\pi$ formula, observe that $A:=\sum_{n=0}^\infty \frac{(-1)^n}{2n+1}$ converges by the alternating series test, so Abel tells us $\lim_{x\nearrow 1} \arctan(x)=A$. As $\arctan(x)$ is continuous on $\mathbb R$, indeed we have $\arctan(1)=A$.


text:
\begin{document}

\title[Spectra of Tukey types]{Spectra of Tukey types of ultrafilters on Boolean algebras}

\author[J. A. Brown]{Jennifer A. Brown}
\email{jennifer.brown@csuci.edu}
\address{Department of Mathematics\\  California  State University - Channel Islands\\ One University Drive \\ Camarillo, CA 93012 U.S.A.}

\author[N. Dobrinen]{Natasha
  Dobrinen}
\email{natasha.dobrinen@du.edu}
\urladdr{http://web.cs.du.edu/~ndobrine}
\address{Department of Mathematics\\
  University of Denver \\
   2280 S Vine St\\ Denver, CO \ 80208 U.S.A.}

\thanks{Dobrinen was supported by  National Science Foundation Grant DMS-1301665.}

\subjclass[2010]{Primary: 06E05, Secondary:
03G05,
06A07,
03E04}

\keywords{Boolean algebra, pseudo-tree algebra, Tukey, ultrafilter}

\begin{abstract}
Extending recent investigations on  the  structure  of  Tukey types of ultrafilters on $\mathcal{P}(\om)$ to Boolean algebras in general, we classify the  spectra of Tukey types of ultrafilters for several classes of Boolean algebras, including interval  algebras, tree algebras,  and  pseudo-tree algebras.
\end{abstract}

\maketitle

\section{Introduction}\label{sec.intro}

The structure of Tukey types of ultrafilters on $\om$ is the subject  of much recent and ongoing research.
This line of research was  reignited, after Isbell's study in \cite{Isbell65}, by   Milovich in \cite{Milovich08}.
One of the interests in this research stems from the connection via Stone duality  between Tukey types of ultrafilters on $\om$ and cofinal types of neighborhood bases on the \v{C}ech-Stone compactification $\beta\om$ of the natural numbers and its \v{C}ech-Stone remainder $\beta\om\setminus\om$.
Recently, the structure of the Tukey types of ultrafilters on $\om$ has undergone an explosion of activity, starting with \cite{Dobrinen/Todorcevic11} of
Dobrinen and Todorcevic,
and continuing in
work of Milovich in \cite{Milovich12},  Raghavan and Todorcevic in \cite{Raghavan/Todorcevic12},
further work of Dobrinen and Todorcevic in
\cite{Dobrinen/Todorcevic14}, \cite{Dobrinen/Todorcevic15},
Blass, Dobrinen, and Raghavan in \cite{Blass/Dobrinen/Raghavan13},
Dobrinen, Mijares, and Trujillo in \cite{Dobrinen/Mijares/Trujillo14}, and most recently Dobrinen in \cite{Dobrinen14}.
These lines of study have all been focused  on clarifying the structure of Tukey types of ultrafilters on $\om$.
In particular, the aforementioned works provide good understanding of the Tukey structure  for a large class of  ultrafilters possessing some means of diagonalization, in particular, p-points.
The reader is referred to the recent survey article \cite{Dobrinen13} for more background.

There remain important open problems regarding Tukey types of ultrafilters on $\om$.
One of the most prominent open problems is due to Isbell.
In \cite{Isbell65}, Isbell showed that there are ultrafilters on $\om$ which have the maximum Tukey type, namely $([\mathfrak{c}]^{<\om},\sse)$.
He then asked whether there are ultrafilters on $\om$ which do not have the maximum Tukey type.
By work in \cite{Dobrinen/Todorcevic11}, p-points are never Tukey maximum.  However, Shelah constructed   a model of ZFC in which there are no p-points (see \cite{ProperForcingBK}),
so what remains of Isbell's problem is the following.
\begin{problem}\label{problem.Isbell}
Is there a model of ZFC in which all nonprincipal ultrafilters have the maximum Tukey type?
\end{problem}

Milovich showed in \cite{Milovich08} that there is a nonprincipal ultrafilter $\mathcal{U}$ on $\omega$ such that $(\mathcal{U},\contains)$ is not Tukey maximum if and only if there is a nonprincipal  ultrafilter $\mathcal{V}$ on $\omega$ such that $(\mathcal{V},\contains^*)$ is not Tukey maximum.
Thus,  Isbell's problem for ultrafilters on the Boolean algebra $\mathcal{P}(\om)$ is equivalent to the  problem for ultrafilters on the Boolean algebra
$\mathcal{P}(\om)/ \fin$.

In this paper,
we  expand the investigation of the Tukey structure of ultrafilters to the general class of all Boolean algebras.
The main motivation  is  the analogue of  Isbell's problem for Boolean algebras in general:
\begin{problem}\label{q.IsbellBA}
Characterize the class of Boolean algebras  for which all its nonprincipal ultrafilters have the maximum Tukey type.
Further, characterize the class of Boolean algebras which have a nonprincipal ultrafilter which is not of maximum Tukey type.
\end{problem}
By understanding the characteristics of  Boolean algebras for which we can prove in ZFC whether or not it has more than one Tukey type of nonprincipal ultrafilter,
we hope to gain new insight and methods for solving Isbell's problem on $\mathcal{P}(\omega)$ and $\mathcal{P}(\om)/\fin$.

The second motivation for this line of work is to use the structure of Tukey types of ultrafilters as a means of classifying Boolean algebras.
Tukey theory has been successfully used to classify  partial orders.
This is especially important in  cases when isomorphism is too strong a notion to gain any meaningful information.
The seminal works of \cite{TodorcevicDirSets85}, \cite{Todorcevic96}, and \cite{Solecki/Todorcevic04} used Tukey reducibility to classify
directed, undirected, and analytic partial orders, respectively.
In a similar vein, the structure of  the Tukey types of ultrafilters on  Boolean algebras can be used as a means for a classifying Boolean algebras.
Given a Boolean algebra $\bB$, it follows from  Stone duality that
the Tukey type of an ultrafilter $\mathcal{U}$ on $\bB$ is the same as the cofinal type of the neighborhood basis of $\mathcal{U}$ in the Stone space of $\bB$.
Thus, the study of Tukey types of ultrafilters on Boolean algebras is equivalent to the study of cofinal types of neighborhood bases of Boolean spaces, that is, zero-dimensional compact Hausdorff spaces.
Those  Boolean algebras with similar Tukey spectra have similar topological properties in their Stone spaces, as the collection of all Tukey types of ultrafilters on a Boolean algebra  is equal to  the  collection of all cofinal types of  neighborhood bases of points in the Stone space.

Before stating more precise questions and basic facts,
we review the relevant definitions.
A partial order $(P,\le)$ is {\em directed} if for any two $p,q\in P$, there is an $r\in P$ such that $p\le r$ and $q\le r$.
An ultrafilter on a Boolean algebra $\bB$ is  simply a maximal filter on $\bB$.
Letting $\le$ denote the natural partial ordering on a Boolean algebra $\bB$ (defined by $a\le b$ if and only if $a\wedge b=a$),
we point out that  for any ultrafilter $\mathcal{U}$ on a Boolean algebra $\bB$,
$(\mathcal{U},\ge)$ is a directed partial ordering.
Although Tukey reducibility can be defined for transitive relations in general, we shall assume here that all partial orders discussed are directed,  since this article concentrates on ultrafilters.

Given $(P,\le_P)$,
a subset $X\sse P$ is {\em cofinal} in $P$ if for each $p\in P$, there is an $x\in X$ such that $p\le_P  x$.
A  map $f \colon (P,\le_P)\ra (Q,\le_Q)$ is {\em cofinal} if for each cofinal $X\sse P$, the image $f[X]$ is cofinal in $Q$.
A set $X\sse P$ is {\em unbounded} if there is no upper bound for $X$ in $P$; that is, there is no
$p\in P$ such that for each $x\in X$, $x\le_P p$.
A map $g \colon (P,\le_P)\ra(Q,\le_Q)$ is {\em unbounded} or {\em Tukey}  if for each unbounded $X\sse P$, the image $g[X]$ is unbounded in $Q$.
Schmidt showed  in \cite{Schmidt55} that the existence of a cofinal map from $(P,\le_P)$ to $(Q,\le_Q)$  is equivalent to the existence of a Tukey map from $(Q,\le_Q)$ to $(P,\le_P)$.
We say that $(P,\le_P)$ is {\em Tukey reducible to} $(Q,\le_Q)$, and write   $(P,\le_P)\le_T (Q,\le_Q)$, if there is  a cofinal map from $(Q,\le_Q)$ to $(P,\le_P)$ (\cite{Tukey40}).
We say that
$(P,\le_P)$ is {\em Tukey equivalent to} $(Q,\le_Q)$, and write $(P,\le_P)\equiv_T (Q,\le_Q)$, if and only if
$(P,\le_P)\le_T (Q,\le_Q)$ and $(Q,\le_Q)\le_T (P,\le_P)$.

It follows from work of Schmidt in \cite{Schmidt55} and is implicit in work of Tukey \cite{Tukey40} that, for each infinite cardinal $\kappa$,
the directed partial ordering  $([\kappa]^{<\om},\sse)$  is the maximum among all Tukey types of directed partial orderings of cardinality $\kappa$.
That is, every directed partial ordering of cardinality $\kappa$ is Tukey reducible to  $([\kappa]^{<\om},\sse)$. The minimal Tukey type is 1 (the one-element partially ordered set). An ultrafilter partially ordered by $\geq$ has this minimal Tukey type if and only if it is principal. For directed partial orderings,  Tukey types and cofinal types coincide.
(See \cite{TodorcevicDirSets85} for more background.)

An ultrafilter $\mathcal{U}$ on a Boolean algebra $\bB$ has the {\em maximum Tukey type}
if  $(\mathcal{U},{\ge})\equiv_T([|\bB|]^{<\om},{\sse})$, which is the maximum possible cofinal type for a directed partial ordering of cardinality $|\bB|$.
Isbell's result in \cite{Isbell65} that there is an ultrafilter on $\om$ which has maximum Tukey type
 led us to ask whether this is true for   Boolean algebras in general:
Given a Boolean algebra, is there an ultrafilter which has the maximum Tukey type?
We will show  that this is not the case: there are several classes of Boolean algebras which do not have any ultrafilters with the maximum Tukey type, the uncountable interval algebras being the simplest of these (see Theorem \ref{interval algebras}).
This along with Problem \ref{q.IsbellBA}   led to the following collection of questions which we investigate.
Our intuition was that  Boolean algebras with strong structure would yield simple Tukey structures.

\begin{question}\label{q.existsmax}
For which Boolean algebras  is there an ultrafilter which has the maximum Tukey type?
\end{question}

\begin{question}\label{q.onlymax}
Are there Boolean algebras on which all ultrafilters have the maximum Tukey type?
\end{question}

\begin{question}\label{q.existsnonmax}
Which Boolean algebras have ultrafilters with non-maximum Tukey type?
\end{question}

\begin{question}\label{q.onlynonmax}
Can we characterize those   Boolean algebras  all of whose ultrafilters have Tukey type strictly below the maximum?
\end{question}

We answer these questions for certain classes of Boolean algebras by obtaining the finer results of classifying their Tukey spectra.
By the {\em Tukey  spectrum} of a Boolean algebra $\bB$, denoted Ts$(\bB)$, we mean the  collection of all Tukey types of  ultrafilters on $\bB$ partially ordered by Tukey reduction.
We use the terminology {\em Tukey spectra} of a class $\mathcal{C}$ of Boolean algebras to mean the collection  $\{$Ts$(\bB):\bB\in\mathcal{C}\}$.
The following is the main focus of this paper.

\begin{problem}\label{q.Ts}
Given a Boolean algebra, find its Tukey spectrum.
\end{problem}

We solve  Problem \ref{q.Ts} for the classes of  free Boolean algebras,  superatomic Boolean algebras generated by almost disjoint families, interval  algebras, tree algebras,  and  pseudo-tree algebras.

Section \ref{sec.top}
concentrates on classes of Boolean algebras which  have an ultrafilter with maximum Tukey type.
We present  conditions guaranteeing the existence of an ultrafilter with the maximum Tukey type, providing some answers to  Question \ref{q.existsmax}.
In particular,
 Theorem \ref{thm.indepimpliestop} shows
that every infinite Boolean algebra with  an independent family of maximum cardinality has an ultrafilter with maximum Tukey type.
In Fact \ref{prop.freealgchar},
we point out that the class of free Boolean algebras answers Question \ref{q.onlymax} positively.
It is then natural to ask whether the completion of a free Boolean algebra has Tukey spectrum consisting of only the maximum Tukey type.
In Theorem \ref{thm.cohennot}  we rule out certain non-maximum Tukey types:  no finite product of
regular cardinals is in the Tukey spectrum of the completion of a free Boolean algebra on infinitely many generators.
In
Theorem \ref{thm.adfamily} we find the Tukey spectra of superatomic Boolean algebras generated by almost disjoint families.
In particular,  the minimum and maximum Tukey types are always attained.

In Section \ref{sec.IntAlg}, we  classify the Tukey spectra  of the families of interval algebras, tree algebras, and pseudo-tree algebras.
Theorem \ref{interval algebras}
classifies the Tukey spectrum of  any interval algebra as a collection of products of two cardinals which are determined by adjutting initial and coinitial chains in the linear order.
It follows that
the Tukey spectrum of the interval algebra of any uncountable linear order  does not include the maximum Tukey type.
Theorem \ref{tree algebras} characterizes the Tukey types of ultrafilters in tree algebras as the product of the cofinality of an initial chain in the tree with the weak product of the cardinality of its set of immediate successors.
This immediately leads to Theorem \ref{c.spectrum of tree algebra} which classifies the Tukey spectra of tree algebras.
Lemma \ref{lem.lambdafan}
distills the essential structure of a set of approximate immediate successors of an initial chain in terms of a $\lambda$-fan (see Definition \ref{def.lambdafan}).
This is used to
 classify  the Tukey spectra of pseudo-tree algebras
in Theorem \ref{p.when pseudo-tree algebras have top type ult} in terms of the product of an initial chain $C$ and the weak product of the cardinals determined by the $\lambda$-fan of approximate immediate successors above $C$.

In addition to finding the Tukey spectra for these classes of Boolean algebras,
we
show that for certain prescribed sets of partial orders, a Boolean algebra can be constructed which contains those partial orders in its Tukey spectrum.
This is done for interval algebras in
Fact \ref{f.attainable types for interval algebras},
and for  pseudo-tree algebras in
Proposition \ref{finite product types attained}, which also takes care of tree algebras.

We conclude the introduction with some notation and basic facts which will be useful throughout the paper.
A function $f \colon (P,\le_P)\ra (Q,\le_Q)$ is called {\em monotone} if whenever $p\le_P p'$ then $f(p)\le_Q f(p')$.

\begin{fact}\label{fact.mono}
\begin{enumerate}
\item
Monotone maps with cofinal images are cofinal maps.
\item
Isomorphic partial orders have the same Tukey type.
\end{enumerate}
\end{fact}

For $\kappa, \mu$ cardinals, the partial order $\leq$ on $\kappa \times \mu$ is defined coordinate-wise:\ $(\alpha, \beta) \leq (\alpha', \beta')$ if and only if $\alpha \leq \alpha'$ and $\beta \leq \beta'$.
More generally, we fix the following notation.
\begin{defn}\label{def.productofcards}
Given a collection of cardinals $\{\kappa_i:i\in I\}$ for some index set $I$,
  $\prod_{i\in I}\kappa_i$ denotes the collection of all functions $f \colon I\ra \bigcup\{\kappa_i:i\in I\}$ such that for each $i\in I$, $f(i)\in\kappa_i$.
The partial ordering $\le$ on  $\prod_{i\in I}\kappa_i$ is coordinate-wise:
 For $f,g\in  \prod_{i\in I}\kappa_i$, $f\le g$ if and only if for all $i\in I$, $f(i)\le g(i)$.
\end{defn}

\begin{fact}\label{facts.useful}
\begin{enumerate}
\item
For any infinite cardinal $\kappa$,
every directed partial ordering of cardinality less than or equal to $\kappa$ is Tukey reducible to
$([\kappa]^{<\om},\sse)$.
\item
Let $\mathcal{U}$ be an ultrafilter on  a Boolean algebra $\bB$, and let $\kappa=|\bB|$.
Then $(\mathcal{U},\ge)\equiv_T([\kappa]^{<\om},\sse)$
if and only if
there is a subset $\mathcal{X}\sse\mathcal{U}$ of cardinality $\kappa$ such that for each infinite $\mathcal{Y}\sse\mathcal{X}$,
$\mathcal{Y}$ is unbounded in $\mathcal{U}$.
\item
$(\om,\le)\equiv_T([\om]^{<\om},\sse)$.
\item
For any uncountable cardinal $\kappa$, $\topkappa >_T (\kappa, {\leq})$.
\item
For any infinite cardinal $\kappa$ and any $n<\omega$, $(\kappa, \leq) \equiv_T (\prod_{i<n}\kappa, \leq)$.
\item Let $\mathcal{U}$ be an ultrafilter on  a Boolean algebra $\bB$, and let $G \subseteq \bB$ be a filter base for $\U$. Then $(\U, \supseteq) \equiv_T (G, \supseteq)$.
\end{enumerate}
\end{fact}

\begin{proof}
(1) follows from work of Schmidt in \cite{Schmidt55}.
The proof of (2) is very similar to the proof of Fact 12 in \cite{Dobrinen/Todorcevic11}.
(3) is due to
Day in \cite{Day44}.
(4) follows from (1) along with the fact that every countably infinite subset of an uncountable cardinal $\kappa$ is bounded in $\kappa$.
To show (5),
let $\kappa \geq \omega$ and $n<\omega$. Define $f \colon (\kappa, \leq) \to (\prod_{i<n}\kappa, \leq)$ by $f(\alpha)=\langle \alpha, \dots, \alpha \rangle$ (the element of $(\prod_{i<n}\kappa, \leq)$ constant at $\alpha$). Then $f$ is an unbounded cofinal map. For (6), note that a filter base $G$ for $\U$ is a cofinal subset of $\U$. Then (6) follows by Fact 3 in \cite{Dobrinen/Todorcevic11}.
\end{proof}

\section{Boolean algebras attaining the maximum Tukey type}\label{sec.top}

It is well-known that for each infinite  cardinal $\kappa$,
there is an ultrafilter on $\mathcal{P}(\kappa)$ with maximum Tukey type.
(This follows from combining work of Isbell in \cite{Isbell65} and Schmidt in \cite{Schmidt55}.)
Such an ultrafilter may be constructed using an independent family on $\kappa$ of cardinality $2^{\kappa}$.
We begin by showing that this construction generalizes to any infinite Boolean algebra $\bB$ with an independent family of cardinality $|\bB|$.

\begin{thm}\label{thm.indepimpliestop}
If $\bB$ is an infinite  Boolean algebra with an independent family of cardinality $|\bB|$,
then there is an ultrafilter $\mathcal{U}$ on $\bB$ such that $(\mathcal{U},\ge)\equiv_T([|\bB|]^{<\om},\sse)$.
\end{thm}

\begin{proof}
Let $\bB$ be any infinite  Boolean algebra
 with an
 independent family $\mathcal{I}=\{a_{\al}:\al<|\bB|\}$, and let $\kappa$ denote $|\bB|$.
Define $\mathcal{J}=\{-b:b\in \bB$ and $\{\al<\kappa: b\le a_{\al}\}$ is infinite$\}$.
We  first show that $\mathcal{I}\cup\mathcal{J}$ has the finite intersection property.
Let $m,n<\om$, $\al_i$ $(i\le m)$ be distinct members of $\kappa$, and let
$b_j$ $(j\le n)$ be distinct members of $\mathcal{J}$.
Since each $b_j$ is below $a_{\al}$ for infinitely many $\al<\kappa$,
we may choose distinct $\beta_j$ ($j\le n$) such that for each $j\le n$,  $b_j\le a_{\beta_j}$,
and moreover $\beta_j\not\in \{\al_i:i\le m\}$.
Since $\mathcal{I}$ is independent it follows that $\bw_{i\le m} a_{\al_i}\wedge\bw_{j\le n}(-a_{\beta_j})>\bo$.
Since each $b_j\ge -a_{\beta_j}$,
we have that $\bw_{i\le m} a_{\al_i}\wedge\bw_{j\le n}b_j>\bo$.

Let $\mathcal{F}$ be the filter generated by $\mathcal{I}\cup\mathcal{J}$.
$\mathcal{F}$ is a proper filter, since its generating set has the finite intersection property.

\begin{claim} $(\mathcal{F},\ge)\equiv_T([\kappa]^{<\om},\sse)$.
\end{claim}

\begin{proof}
It  suffices to show that
 $(\mathcal{F},\ge)\ge_T([\kappa]^{<\om},\sse)$,
 since  $\mathcal{F}$ being a directed partial order of size $\kappa$ implies that $(\mathcal{F},\ge)\le_T([\kappa]^{<\om},\sse)$.
Define $f \colon [\kappa]^{<\om}\ra\mathcal{F}$ by $f(F)=\bw_{\al\in F}a_{\al}$, for each $F\in[\kappa]^{<\om}$.
We claim that $f$ is a Tukey map.
To see this, let $\mathcal{X}\sse[\kappa]^{<\om}$ be unbounded in $([\kappa]^{<\om},\sse)$.
Then $\mathcal{X}$ must be infinite.
The $f$-image of $\mathcal{X}$ is $\{\bw_{\al\in F}a_{\al}:F\in\mathcal{X}\}$.
Any lower bound $b$ of $\{\bw_{\al\in F}a_{\al}:F\in\mathcal{X}\}$ would have to have the property that
 $b\le\bw_{\al\in\bigcup\mathcal{X}}a_{\al}$.
But $\bv_{\al\in\bigcup\mathcal{X}}-a_{\al}$ is in $\mathcal{B}$, since $\bigcup\mathcal{X}$ is  infinite; so  the complement of $\bw_{\al\in\bigcup\mathcal{X}}a_{\al}$ is in $\mathcal{F}$.
Since $\mathcal{F}$ is a proper filter,
$\mathcal{F}$ contains no members below
$\bw_{\al\in\bigcup\mathcal{X}}a_{\al}$.
It follows that
 the $f$ image of $\mathcal{X}$ is unbounded in $\mathcal{F}$.
Therefore $f$ is a Tukey map and the claim holds.
\end{proof}

Let $\mathcal{U}$ be any
 ultrafilter on $\bB$ extending $\mathcal{F}$.
Then  $(\mathcal{F},\ge)\le_T(\mathcal{U},\ge)$, since the identity map on $(\mathcal{F},\ge)$ is a Tukey map.
Hence, $(\mathcal{U},\ge)\equiv_T([\kappa]^{<\om},\sse)$.
\end{proof}

The next theorem follows immediately by an application of  the Balcar-Fran\v{e}k Theorem, which states that every infinite complete Boolean algebra has an independent subset of cardinality that of the algebra (see Theorem 13.6 in \cite{KoppelbergHB}).

\begin{thm}\label{cor.complete.top}
Every infinite complete Boolean algebra has an ultrafilter with maximum Tukey type.
\end{thm}

\begin{proof}
By the Balcar-Fran\v{e}k Theorem,
every infinite  complete Boolean algebra $\bB$ has an independent family of cardinality $|\bB|$.
By Theorem \ref{thm.indepimpliestop}, there is an ultrafilter $\mathcal{U}$ on $\bB$ such that
$(\mathcal{U},\ge)\equiv_T([|\bB|]^{<\om},\sse)$.
\end{proof}

We mention  the following theorem of Shelah  giving sufficient conditions for a Boolean algebra to have an independent family of maximal size.

\begin{thm}[Shelah, (Theorem 10.1 in \cite{KoppelbergHB})]\label{thm.Shelah10.1}
Assume $\kappa,\lambda$ are regular infinite cardinals such that $\mu^{<\kappa}<\lambda$ for every cardinal $\mu<\lambda$, and that $\bB$ is a Boolean algebra satisfying the $\kappa$-chain condition.
Then every $X\sse\bB$ of size $\lambda$ has an independent subset of $Y$ of size $\lambda$.
\end{thm}

Thus, if $\bB$ has the $\kappa$-chain condition, $|\bB|=\lambda$,  and for all $\mu<\lambda$, $\mu^{<\kappa}<\lambda$,
then  $\bB$  contains an independent subset of size $|\bB|$.
Theorem \ref{thm.indepimpliestop} then implies that $\bB$ has an ultrafilter with maximum Tukey type.

The next theorem shows that every ultrafilter on a
  free Boolean algebra  has  maximum Tukey type.
Thus, for each infinite cardinal $\kappa$, the spectrum of the Tukey types of ultrafilters on $\Clop(2^{\kappa})$ is precisely $\{([\kappa]^{<\om},\sse)\}$.

\begin{fact}\label{prop.freealgchar}
For each infinite cardinal $\kappa$ and each ultrafilter $\mathcal{U}$ on $\Clop(2^{\kappa})$,
$(\mathcal{U},{\ge})\equiv_T([\kappa]^{<\om},\sse)$.
\end{fact}

\begin{proof}
Let $\kappa$ be an infinite cardinal.
The basic clopen sets of Clop$(2^{\kappa})$ are the sets
$c_s=\{f\in 2^{\kappa}:f\contains s\}$,
where $s$ is any function from a finite subset of $\kappa$ into $2$.
Given an $x\in 2^{\kappa}$,
define a map $f$ from $[\kappa]^{<\om}$ into the neighborhood base of $x$ by
letting $f(F)=c_{x\re F}$.
Then $f$ is a cofinal and unbounded map, so the neighborhood base of $x$ has cofinal type exactly $([\kappa]^{<\om},\sse)$.
Thus, every point in the Stone space $2^{\kappa}$ has neighborhood base of maximum Tukey type.
By Stone duality, this implies that each ultrafilter on Clop$(2^{\kappa})$ is Tukey equivalent to $([\kappa]^{<\om},\sse)$.
\end{proof}

\begin{rem}
The Stone space of each free Boolean algebra is homogeneous; that is, given any infinite cardinal $\kappa$,
for any two ultrafilters $\mathcal{U},\mathcal{V}$ on Clop$(2^{\kappa})$, there is a homeomorphism from Ult$($Clop$(2^{\kappa}))$ onto itself mapping $\mathcal{U}$ to $\mathcal{V}$
(see Exercise 4, page 139 in \cite{KoppelbergHB}).
Since  a homeomorphism maps any neighborhood base of $\mathcal{U}$ cofinally to any neighborhood base of $\mathcal{U}$, and vice versa,
 $\mathcal{U}$ is Tukey equivalent to $\mathcal{V}$.
In fact, homogeneity of the Stone space of any Boolean algebra implies  all its ultrafilters have the same Tukey type.
However, this says nothing about what  that Tukey type is.
We shall see in  Section  \ref{sec.IntAlg}
that it is possible to have an interval algebra in which all the ultrafilters have the same Tukey type $\kappa$, which is not the maximum type if $\kappa$ is an uncountable cardinal.
\end{rem}

Next, we investigate the Tukey spectra of completions of free algebras.
By Theorem \ref{cor.complete.top}, the completion  of Clop$(2^{\kappa})$, denoted
 r.o.(Clop$(2^{\kappa})$),  always has an ultrafilter of the maximum  Tukey type $([2^{\kappa}]^{<\om},\sse)$.
In particular, the Cohen algebra r.o.(Clop$(2^{\om})$) has an ultrafilter of type $([\mathfrak{c}]^{<\om},\sse)$.
This leads us to the following question.

\begin{question}\label{q.rofree.below}
Do all the ultrafilters in  the completion of a free Boolean algebra  have maximum Tukey type?
\end{question}

In Theorem \ref{thm.cohennot}, we will rule out some
 possible  Tukey types  below the top for all completions of  free algebras.
We begin with two  propositions in which certain completeness or chain condition hypotheses rule out certain Tukey types of ultrafilters.

\begin{prop}\label{prop.kcomplete}
If $\kappa\ge \om$ and  $\bB$ is a $\kappa^+$-complete atomless Boolean algebra, then  $\bB$ has no ultrafilters of Tukey type $(\kappa,\le)$.
\end{prop}

\begin{proof}
Let $\mathcal{U}$ be an ultrafilter on $\bB$ and suppose toward a contradiction that there is a strictly decreasing sequence $\lgl b_{\al}:\al<\kappa\rgl$ cofinal in, and thus generating, $\mathcal{U}$.
Without loss of generality, we may assume that for each limit ordinal $\gamma<\kappa$,
$b_{\gamma}=\bigwedge_{\al<\gamma} b_{\al}$ and that $b_0=\bone$.
Since $\lgl b_{\al}:\al<\kappa\rgl$ generates an ultrafilter, it follows that $\bigwedge_{\al<\kappa}b_{\al}=\bo$.
For each $\al<\kappa$, define $a_{\al}=b_{\al}\wedge -b_{\al+1}$.
Since $\bB$ is atomless, there are non-zero $a_{\al, 0},a_{\al, 1}$
partitioning $a_{\al}$.
Let $c_i=\bigvee_{\al<\kappa} a_{\al,i}$, for $i<2$.
Then $c_0\vee c_1=\bone$ and $c_0\wedge c_1=\bo$;
so exactly one of $c_0,c_1$ must be in $\mathcal{U}$.
But for each $i<2$, we have that $c_i\not\ge b_{\al}$ for all $\al<\kappa$.
Since $\lgl b_{\al}:\al<\kappa\rgl$ generates $\mathcal{U}$, this implies that neither of $c_0,c_1$ is in $\mathcal{U}$, contradiction.
\end{proof}

\begin{prop}\label{prop.kcc}
Let $\kappa$ be a regular uncountable cardinal.
If $\bB$ is $\kappa$-c.c.,
then for all $\lambda\ge\kappa$, $\bB$ has no ultrafilters of Tukey type $(\lambda,\le)$.
\end{prop}

\begin{proof}
$\bB$ is $\kappa$-c.c. implies there are no strictly decreasing chains of order type $\lambda$ in $\bB$ for any $\lambda\ge\kappa$.
In particular, no ultrafilter in $\bB$ can be generated by a strictly decreasing chain of order type $\lambda$.
\end{proof}

The following fact is due to Isbell.
Recall that  a partial ordering $(Q,\le_Q)$ is {\em relatively complete} if every subset of $Q$ which is bounded from below has a greatest lower bound  in $Q$.

\begin{prop}[Isbell, \cite{Isbell65}]\label{prop.monotone}
Let $(P,\le_P)$ and $(Q,\le_Q)$ be directed partial orderings. If $Q$ is relatively complete, then $P\ge_T Q$ if and only if there exists a monotone map $f \colon P\ra Q$  which has cofinal range.
\end{prop}

\begin{thm}\label{thm.cohennot}
Let $\kappa$ be an infinite cardinal.
Then each  ultrafilter on the completion of the free algebra on $\kappa$ generators  is not Tukey reducible to
$\prod_{i\le n}\kappa_i$ for any finite  collection of regular cardinals $\{\kappa_i:i\le n\}$.
\end{thm}

\begin{proof}
Let $\kappa$ be an infinite cardinal and  $\mathcal{U}$ be any ultrafilter on $\ro(\Clop(2^{\kappa}))$.
We will show that for any collection of finitely many regular cardinals $\kappa_i$, $i\le n$, $\prod_{i\le n}\kappa_i\not\ge_T\mathcal{U}$.
It suffices  to consider only infinite cardinals $\kappa_i$, as
all ultrafilters on $\ro(\Clop(2^{\kappa}))$ are nonprincipal since $\ro(\Clop(2^{\kappa}))$ is atomless.
Since $\mathcal{U}$ is an ultrafilter, it is upwards closed.
In particular, the directed partial ordering $(\mathcal{U},\ge)$ is  relatively complete.
Thus, by Proposition \ref{prop.monotone},
whenever $(P,\le_P)\ge_T(\mathcal{U},\ge)$, there is a monotone cofinal map witnessing this.

Suppose $n=0$ and let $\kappa_0$ be any regular infinite  cardinal.
If $\kappa_0\ge_T\mathcal{U}$, then by Proposition \ref{prop.monotone}, there is a monotone cofinal map from $\kappa_0$ into $\mathcal{U}$.
Any monotone map will take $\kappa_0$ to a decreasing  sequence in $\mathcal{U}$, which is either eventually constant or else has a strictly decreasing subsequence of cofinality $\kappa_0$.
Propositions \ref{prop.kcomplete} and \ref{prop.kcc} imply that $\mathcal{U}$ is  not generated by any strictly decreasing infinite sequence of members of $\mathcal{U}$.
Since $\mathcal{U}$ is not principal it cannot be generated by a single member.
Thus, $\kappa_0\not\ge_T\mathcal{U}$.

Now suppose that $n\ge 1$ and
given any infinite regular cardinals $\kappa_i$, $i<n$,
$\prod_{i<n}\kappa_i\not\ge_T\mathcal{U}$.
Let $\{\kappa_i:i\le n\}$ be any collection of infinite  regular cardinals, and without loss of generality, assume they are indexed in strictly increasing order.
 Suppose that $f \colon \prod_{i\le n}\kappa_i\ra\mathcal{U}$ is a monotone  map into $\mathcal{U}$.
Fix a  sequence $\bar{\al}\in\prod_{i<n}\kappa_i$.
$f$ maps the strictly increasing sequence $\lgl {\bar{\al}}^{\frown}\beta: \beta\in \kappa_n\rgl$ in
$\prod_{i\le n}\kappa_i$
  to a decreasing (not necessarily strictly decreasing) sequence in $\mathcal{U}$, since $f$ is monotone.
Since $\kappa_n$ is uncountable and $\mathcal{U}$ has no uncountable strictly decreasing sequences,  there is some  $\beta(\bar{\al})\in\kappa_n$  such that
 $f({\bar{\al}}^{\frown}\beta(\bar{\al}))=
\min\{f({\bar{\al}}^{\frown}\beta):\beta\in\kappa_n\}$.
Let  $\gamma$ denote
$\sup\{  \beta(\bar{\al}): \bar{\al}\in\prod_{i<n}\kappa_i\}$.
Since $|\prod_{i<n}\kappa_i|=\kappa_{n-1}<\kappa_n$, it follows that
$\gamma<\kappa_n$.
Since $f$ is monotone,
the $f$-image of $\prod_{i\le n}\kappa_i$ is bounded below in $\mathcal{U}$ by the set $\{f(\bar{\al}^{\frown}\gamma):\bar{\al}\in\prod_{i<n}\kappa_i\}$.
By the induction hypothesis, this is not possible, since the set
$\{(\bar{\al})^{\frown}\gamma:\bar{\al}\in\prod_{i<n}\kappa_i\}$ is isomorphic as a partially ordered set to $\prod_{i<n}\kappa_i$.
Thus, $f$ cannot be a cofinal map.

Therefore, there is no monotone cofinal map from $\prod_{i\le n}\kappa_i$ into $\mathcal{U}$.
Hence, by
Proposition \ref{prop.monotone},
 $\prod_{i\le n}\kappa_i\not\ge_T\mathcal{U}$.
\end{proof}

In particular,  the Cohen algebra has  no ultrafilters of Tukey type $1$, $\om$, $\om_1$,  $\mathfrak{c}$, $\om\times\om_1$, or any finite product of regular cardinals $\kappa_i$, $i\le n$, where $\om\le \kappa_0<\kappa_1<\dots<\kappa_n\le \mathfrak{c}$.

\begin{question}
Does $\ro(\Clop(2^{\kappa}))$ have an ultrafilter Tukey equivalent to $\prod_{i\in I}\kappa_i$ for some infinite collection of regular infinite cardinals?
In particular, does the Cohen algebra have an ultrafilter Tukey equivalent to $(\om^{\om},\le)$?
\end{question}

\begin{rem}
Milovich in \cite{Milovich12} defines a preorder to be \textit{cofinally rectangular} if it is cofinally equivalent to the product of some finite  collection of regular cardinals. Theorem \ref{thm.cohennot} shows that all  ultrafilters on the completion of a free Boolean algebra (on infinitely many generators) are not cofinally rectangular.
We will show in
Section \ref{sec.IntAlg}, Theorem \ref{interval algebras},
 that there are Boolean algebras (namely interval algebras) which have only cofinally rectangular ultrafilters.
\end{rem}

The following simple fact shows that each finite-cofinite Boolean algebra has Tukey spectrum of size two, consisting exactly of the minimum and the maximum Tukey types.

\begin{fact}\label{prop.fincofin}
Let $X$ be any infinite set, and let $\bB$ denote the finite-cofinite algebra on $X$.
Then the  ultrafilters on $\bB$ consist exactly of the  principal ultrafilters and the cofinite ultrafilter.
Thus, the Tukey spectrum of $\bB$ is $\{(1,\le), ([\abs{X}]^{<\om},\sse)\}$.
\end{fact}

\begin{proof}
The ultrafilter of cofinite subsets of $X$ is isomorphic to $[|X|]^{<\om}$.
If an ultrafilter on $\bB$ contains a finite set, then it is a principal ultrafilter.
\end{proof}

This section closes with the Tukey spectra of Boolean algebras  generated by some almost disjoint family on an infinite set.
Let $\lambda$ be an infinite  cardinal.
A family $\mathcal{A}\sse\mathcal{P}(\lambda)$ is
{\em almost disjoint}
if  for all pairs $a,b\in\mathcal{A}$,  $|a\cap b|<\om$.
Given an almost disjoint family $\mathcal{A}\sse\mathcal{P}(\lambda)$,
the {\em almost disjoint Boolean algebra generated by $\mathcal{A}$} is
the subalgebra  of $\mathcal{P}(\lambda)$ generated by $\mathcal{A}\cup [\lambda]^{<\om}$.
Any Boolean algebra generated from an almost disjoint family is superatomic.
(See Example 0.1 on page 721 in \cite{RoitmanHBBAVol3}.)

\begin{thm}\label{thm.adfamily}
Let $\mathcal{A}$ be an almost disjoint family on an infinite cardinal $\lambda$ with $|\mathcal{A}|=\kappa$,
and let $\bB$ denote the  subalgebra  of $\mathcal{P}(\lambda)$ generated by $\mathcal{A}$.
Then every ultrafilter on $\bB$  has Tukey type $1$ or  $[\mu]^{<\om}$ for some $\om\le \mu\le\kappa$.
The minimum and maximum types, $1$ and $[\kappa]^{<\om}$, are  always realized.
For $\om\le\mu<\kappa$,  $[\mu]^{<\om}$ is realized as the Tukey type of some ultrafilter on $\bB$ if and only if
 there is an $a\in\mathcal{A}$ such that the set $\{a\cap-b:b\in\mathcal{A}\setminus\{a\}\}$ has cardinality $\mu$.
\end{thm}

\begin{proof}
Let $\mathcal{A}$ be an almost disjoint family on an infinite cardinal $\lambda$.
Let $\bB$ denote the subalgebra of $\mathcal{P}(\lambda)$ generated by $\mathcal{A}$, and let $\kappa=|\bB|$.
The ultrafilters on $\bB$ are of three possible forms, each of which is realized:
 principal,  generated by $\{-a:a\in\mathcal{A}\}$, or generated by $\{a\cap - b: b\in\mathcal{A}\setminus \{a\}\}$ for some $a\in\mathcal{A}$.
The principal ultrafilters have Tukey type $1$.

Suppose
 $\mathcal{U}$ is  the ultrafilter generated by the set $\{-a:a\in\mathcal{A}\}$.
In this case, index the members of $\mathcal{A}$ so that $\mathcal{A}=\{a_{\al}:\al<\kappa\}$.
This ultrafilter is nonprincipal.
As above,   the map $g \colon [\kappa]^{<\om}\ra\mathcal{U}$, given by $g(F)=\bigcap_{\al\in F}-a_{\al}$,  is a monotone cofinal Tukey map.
Therefore, $(\mathcal{U},\ge)\equiv_T([\kappa]^{<\om},\sse)$, since $|\bB|=\kappa$.

For the third type of ultrafilter, fix any $a\in\mathcal{A}$ and enumerate $\mathcal{A}\setminus \{a\}$ as $\{a_{\al}:\al<\kappa\}$, and let $\mathcal{U}$ be the ultrafilter generated by $\{a\}\cup\{-a_{\al}:\al<\kappa\}$.
Let $K\sse\kappa$ be a maximal subset of $\kappa$ such that for all $\al\ne\beta$ in $K$,
$a\cap -a_{\al}\ne a\cap -a_{\beta}$, and let $\mu=|K|$.
Without loss of generality,
suppose $\U$ is nonprincipal, and hence $\mu\ge \om$.
Define a map $g \colon [K]^{<\om}\ra \mathcal{U}$ by
$g(F)=a\cap(\bigcap_{\al\in F}-a_{\al})$, for each $F\in[K]^{<\om}$.
We claim that $g$ is a monotone cofinal and Tukey map.
By definition, it is clear that $g$ is monotone. Since its range is all of $\mathcal{U}$, it is a cofinal map.
To check that $g$ is Tukey,
let $\mathcal{X}\sse [K]^{<\om}$ and suppose that
there is  a bound $b\in\mathcal{U}$ for $\{g(F):F\in\mathcal{X}\}$.
Then  $b\sse a\cap(\bigcap_{\al\in F}-a_{\al})$, for each $F\in\mathcal{X}$.
Letting  $G=\bigcup \mathcal{X}$, we see that
$b\sse a\cap (\bigcap_{\al\in G}-a_{\al})$.
Thus, $G$ must be finite; hence also $\mathcal{X}$ is finite and therefore bounded.
Therefore, $\mathcal{U}\equiv_T[\mu]^{<\om}$.
\end{proof}

\begin{question}
What are the Tukey spectra of superatomic Boolean algebras in general?
\end{question}

Lastly, we state a theorem that will be proved in Section 4: A tree algebra $\treealg T$ of size $\kappa$ has an ultrafilter with maximum Tukey type if and only if the underlying tree $T$ has an initial chain with $\kappa$-many immediate successors. (This is Corollary \ref{U top iff kappa succs of C}; we will also prove in Corollary \ref{p.when pseudo-tree algebras have top type ult} a more general version for pseudo-tree algebras.)

\section{Spectra of Tukey types of interval algebras, tree algebras, and pseudo-tree algebras}\label{sec.IntAlg}

Basic facts about interval algebras and tree algebras can be found in Volume 1 of the Handbook of Boolean Algebras \cite{KoppelbergHB}; basic facts about pseudo-tree algebras which generalize from corresponding tree algebra facts can be found in \cite{Koppelberg/Monk92}. Since pseudo-trees are probably the least well-known of these classes, we provide some background on them here. We follow the notation in \cite{Koppelberg/Monk92}.

A \textit{pseudo-tree} is a partially ordered set $(T, \leq)$ such that for each $t \in T$, the set $T \downarrow t = \{s \in T: s \leq t\}$ is linearly ordered. The pseudo-tree algebra on a pseudo-tree $T$ is generated in the same way as a tree algebra: $\treealg(T)$ is the algebra of sets generated by the ``cones'' $T \uparrow t=\{s \in T: s \geq t\}$, for $t \in T$. A pseudo-tree algebra is thus a generalization of both an interval algebra and a tree algebra, and the following discussion of the correspondence between ultrafilters and initial chains applies to all three classes of Boolean algebras.

Let $T$ be an infinite pseudo-tree with a single root. (It does no harm to assume that all of our pseudo-trees have single roots; any pseudo-tree algebra is isomorphic to a pseudo-tree algebra on a pseudo-tree with a single root (see \cite{Koppelberg/Monk92}).) An initial chain in $T$ is a non-empty chain $C \subseteq T$ such that if $c \in C$ and $t < c$ then $t \in C$. There is a one-to-one correspondence between ultrafilters $\U$ on $\treealg T$ and initial chains in $T$, given by
\[\phi(\U)=\{t \in T: T \cn t \in \U\}.\]
The inverse of this map shows how ultrafilters are generated by sets defined in terms of their corresponding initial chains: for $C$ an initial chain in $T$,
$\phi^{-1}(C)=\langle H_C \rangle,$
where \[H_C=\{(T \cn t) \setminus \bigcup_{s \in S}(T \cn s): t \in C,\ S \textrm{ is a finite antichain of elements }s > C\}\] (where $S$ is allowed to be empty).
This set of generators is closed under finite intersection, and
$(\U, \supseteq) \equiv_T (H_C, \supseteq)$.

Let $C \subseteq T$ be an initial chain. Call a subset $R \subseteq T$ a \textit{set of approximate immediate successors of} $C$ if

(i) $r>C$ for all $r \in R$, and

(ii) for all $s > C$, there is an $r \in R$ such that $C<r\leq s$.

\n Then define \[\varepsilon_C=\min\{\abs{R}: R \textrm{ is a set of approximate immediate successors of } C\}.\]

The character $\chi$ of an ultrafilter $\U$ on $\treealg T$ is the minimum size of a generating set for $\U$. If $C$ is the initial chain corresponding to $\U$, then $\chi(\U)=\max\{\varepsilon_C, \cf C\}$ (see \cite{Brown15}). If $T$ is a tree, then the set $\imm(C)$ of immediate successors of an initial chain $C$ in $T$ is well-defined, even if $C$ does not have a top element, and $\varepsilon_C=\abs{\imm(C)}$.

We describe all possible Tukey types of ultrafilters on interval algebras in Theorem \ref{interval algebras}.
From this, we classify the spectra of Tukey types of all interval algebras. In the terminology of Milovich \cite{Milovich12}, ultrafilters on interval algebras have cofinally rectangular Tukey types. We assume that all linear orders mentioned have least elements. (Where a linear order does not naturally have a least element, we add an element $-\infty$ to $L$ and proceed to build $\intalg L$ as in \cite{KoppelbergHB}.)

For $L$ a linear order and $X \subseteq L$, the coinitiality of $X$, denoted $\ci(X)$, is the least cardinal $\mu$ such that $\mu^*$ is coinitial in $X$.

\begin{thm}\label{interval algebras}
Let $L$ be a linear ordering.
Let $P$ denote the set of pairs of regular cardinals $(\kappa,\mu)$ for which there is an initial chain $C$ in $L$  such that the cofinality of $C$ is $\kappa$ and the coinitiality of $L\setminus C$ is $\mu$.
Then the Tukey spectrum of Intalg $L$ is exactly
$\{(\kappa\times\mu,\le):(\kappa,\mu)\in P\}$.
\end{thm}

\begin{proof}
Let $L$ be a linear order with a first element and set $A=\intalg L$. Since $A$ is also a pseudo-tree algebra, its ultrafilters are associated with initial chains as are those of pseudo-tree algebras.
 Let $\U \in \ult A$ and let $C$ be the initial chain associated with $\U$.
Let $\kappa =\cf C$ and  $\{c_\alpha:\alpha < \kappa\}$ be an increasing cofinal sequence in $C$.
Let
$\mu=\ci(L\setminus C)$ and let
 $\{l_\beta:\beta < \mu\}$ be a decreasing coinitial sequence in $L \setminus C$.
Letting
\[G=\{[c_\alpha, l_\beta): \alpha < \kappa, \beta < \mu\},\]
we see that
 $\U=\langle G \rangle$, and hence $(\U, \supseteq) \equiv_T
(G, \supseteq)$.
Define $f \colon (G, {\supseteq}) \to (\kappa \times \mu)$ by $f([c_\alpha, l_\beta))=(\alpha, \beta)$. One can check that $f$ is an unbounded cofinal map, so that $(G, \supseteq) \equiv_T (\kappa\times\mu,\le)$.
\end{proof}

Thus if $L$ is a linear order and $\U$ is an ultrafilter on $\intalg L$, then there are only three possibilities for the Tukey type of $(\U, \supseteq)$. Letting $C$ be the initial chain corresponding to $\U$, either
\begin{enumerate}
\item $(\U, \supseteq) \equiv_T (\kappa, \leq)$ where $\cf C = \kappa$, or
\item $(\U, \supseteq) \equiv_T (\mu, \leq)$ where   $\ci (L \setminus C) = \mu$, or
\item $(\U, \supseteq) \equiv_T (\kappa \times \mu, \leq)$ where $\cf C = \kappa$ and $\ci (L \setminus C) = \mu$.
\end{enumerate}

(Recall from Fact \ref{facts.useful} (5) that if $\cf C = \kappa = \ci (L \setminus C)$ then $(\U, \supseteq) \equiv_T (\kappa \times \kappa, {\leq}) \equiv_T (\kappa, \leq)$.)

Observe that Fact \ref{facts.useful} (4)  then implies that no uncountable interval algebra $\intalg L$ has an ultrafilter of maximal Tukey type $([\abs{L}]^{<\omega}, \subseteq)$. Countably infinite linear orders always have ultrafilters of top Tukey type:\ let $L$ be a countably infinite linear order. Then $L$ contains a initial chain $C$ with $\cf C = \omega$ or $\ci (L \setminus C) = \omega$; and in any case, if $\U$ is the ultrafilter corresponding to $C$, $(\U, \supseteq) \equiv_T (\omega, \leq) \equiv_T ([\omega]^{<\omega}, \subseteq)$.

Next, we show that  the Tukey spectra of  interval algebras is quite robust.

\begin{fact}\label{f.attainable types for interval algebras}
Given any collection  $P$ of pairs of regular cardinals, each of which is either $1$ or else is infinite, there is a linear order $L$ whose Tukey spectrum
 includes $\{(\kappa\times\mu,\le):(\kappa,\mu)\in P\}$.
\end{fact}

\begin{proof}
Let $\lambda=|P|$ and enumerate the pairs of regular cardinals in $P$ as $\{(\kappa_\alpha, \mu_\alpha): \alpha < \lambda\}$.
For $\alpha < \lambda$, let $X_\alpha$ be a sequence of order type $\kappa_\alpha$, and let $Y_\alpha$ be a sequence of order type $\mu_\alpha^*$. Let
 $L$ be the linear order
$$L=\bigcup_{\al<\lambda}\{\al\}\times
({X_{\al}}^{\frown}Y_{\al})$$
with the lexicographic ordering.
For $\alpha < \lambda$, let $C_\alpha$ denote the set of
those elements of $L$ that are below every element of $Y_\alpha$.
Then $\cf C_\alpha = \cf X_\alpha = \kappa_\alpha$ and $\ci(L \setminus C_\alpha)=\ci Y_\alpha = \mu_\alpha$.
Letting $\U_\alpha$ be the ultrafilter corresponding to $C_\alpha$, it follows that $(\U_\alpha, \supseteq) \equiv_T (\kappa_\alpha \times \mu_\alpha, \leq)$.
\end{proof}

We note that the Tukey spectrum of the interval algebra in the proof of Fact \ref{f.attainable types for interval algebras} may also contain types not among $\{(\kappa \times \mu, \leq): (\kappa, \mu) \in P\}$. For example, if $P=\{(\omega_1, \omega_1)\}$, then the construction gives us $L=\omega_1 + \omega_1^*$, and $\intalg(L)$ has the type $(\omega, \leq)$ in its Tukey spectrum.

Now we attend to the class of tree algebras. All products we mention in what follows will be of the following weak sort:\ for an index set $I$ and a collection of cardinals $\{\kappa_i:i \in I\}$,
let $\prod^{\mathrm{w}}_{i\in I}\kappa_i$ denote the collection of all functions $f\in\prod_{i\in I}\kappa_i$ such that for all but finitely many $i\in I$, $f(i)=0$; again the partial ordering is coordinate-wise. In the special case where the index set $I$ is a cardinal and each $\kappa_i$ is 2, we have the following fact.

\begin{fact}\label{f: top type equiv to a prod}
For any $\kappa$, $\prod^{\mathrm{w}}_{\alpha < \kappa}\{0,1\}\equiv_T \topkappa$.
\end{fact}

\begin{proof} For $F \in [\kappa]^{<\om}$, set $f(F)=\langle e_\alpha: \alpha < \kappa \rangle$ where

\[ e_\alpha = \begin{cases}
1 \textrm{ if } \alpha \in F\\
0 \textrm{ if } \alpha \not\in F
\end{cases}
\]

Then $f$ is an unbounded cofinal map.
\end{proof}

Proposition \ref{treealg of size om has top type ult} and Corollary \ref{U top iff kappa succs of C} characterize those trees $T$ for which  the algebra $\treealg T$ has an ultrafilter of maximal Tukey type $([\abs{T}]^{<\omega},\subseteq)$.

\begin{prop}\label{treealg of size om has top type ult}
If $T$ is a tree of size $\omega$ with a single root, then $\treealg T$ has an ultrafilter of type $([\om]^{<\om}, \subseteq)$.
\end{prop}

\begin{proof}
Let $T$ be a tree of size $\om$ with a single root. Then also $\abs{\treealg T}=\om$.
If there is  some $z \in T$ with $\omega$-many immediate successors $\{s_i:i<\om\}$,
then set $C=T \bl z$ and let $\U=\phi^{-1}(C)$ be the corresponding ultrafilter. Define $a_n \in \treealg T$, for $n < \om$, by $a_n=(T \cn z) \setminus \bigcup_{i<n} (T \cn s_i)$. Then the $a_n$ form a chain of type $\om$ in $(\U, \supseteq )$, so that $(\U, \supseteq) \equiv_T (\om, \leq) \equiv_T ([\omega]^{<\omega}, \subseteq)$.

Otherwise, no $z \in T$ has $\omega$-many immediate successors. Since $T$ has a single root, this means that for all $n<\omega$, $\abs{\operatorname{Lev}_n(T)}<\om$; that is, $T$ is an $\om$-tree. By K\"{o}nig's Lemma, $T$ has an infinite chain $\{c_n:n<\om\}$. Let $C$ be minimal among initial chains containing $\{c_n:n<\om\}$. Let $\U=\phi^{-1}(C)$ be the ultrafilter corresponding to $C$. For each $n<\om$, set $a_n=T \cn c_n$. Then the $a_n$ form a chain of type $\om$ in $( \U, \supseteq)$, so that $(\U, \supseteq) \geq_T (\om, \leq)$. Since $(\om, \leq)$ has the maximum Tukey type for $\om$, $(\U, \supseteq) \equiv_T ( [\omega]^{<\omega}, \subseteq )$.
\end{proof}

\begin{thm}\label{tree algebras}
Let $T$ be a tree, let $\U$ be an ultrafilter on $T$, and let $C$ be the initial chain corresponding to $\U$. Let $\{c_\alpha: \alpha < \cf C\}$ be an increasing cofinal sequence in $C$, and let $\{s_\beta: \beta < \mu\}$ be the set of immediate successors of $C$ in $T$. Then $(\U, \supseteq) \equiv_T (\cf C \times \prod^\mathrm{w}_{\beta < \mu}\{0,1\}, \leq)$.
\end{thm}

\begin{proof}
$\U$ is generated by $G=\{(T \cn c_\alpha) \setminus \bigcup_{\beta \in F}(T \cn s_\beta): \alpha < \cf C, F \in [\mu]^{<\omega}\}$. Define $f \colon (G, \supseteq) \to (\cf C \times \prod^\mathrm{w}_{\beta < \mu}\{0,1\}, \leq)$ by $f((T \cn c_\alpha) \setminus \bigcup_{\beta \in F}(T \cn s_\beta))=\langle \alpha \rangle^{\smallfrown} \langle e_\beta: \beta < \mu\rangle$ where
\[ e_\beta = \begin{cases}
1 \textrm{ if } \beta \in F\\
0 \textrm{ if } \beta \not\in F.
\end{cases}
\]
We claim that $f$ is an unbounded cofinal map. Let $X \subseteq G$ be unbounded. Then either (i) the set \[\{\alpha < \cf C: (T \cn c_\alpha) \setminus \bigcup_{\beta \in F}(T \cn s_\beta) \in X \textrm{ for some } F \in [\mu]^{<\omega}\}\] is unbounded in $\cf C$, or (ii) the set
 \[\{\gamma < \mu: (T \cn c_\alpha) \setminus \bigcup_{\beta \in F}(T \cn s_\beta) \in X \textrm{ for some } \alpha < \cf C, F \in [\mu]^{<\omega} \textrm{ with } \gamma \in F\}\]
 is infinite. In case (i), the set of first coordinates of elements of $f[X]$ is unbounded in $\cf C$. In case (ii), there are infinitely many $\beta < \mu$ at which some element of $f[X]$ has the value 1. In either case, $f[X]$ is unbounded in $(\cf C \times \prod^\mathrm{w}_{\beta < \mu}\{0,1\}, \leq)$.

 Now suppose $X \subseteq G$ is a cofinal subset. Let $p=\langle \alpha, e_0, e_1, \dots, e_\beta, \dots \rangle \in (\cf C \times \prod^\mathrm{w}_{\beta < \mu}\{0,1\}, \leq)$. Set $F=\{\beta < \mu: e_\beta = 1\}$. As $X$ is cofinal in $G$, there is some $x \in X$ such that $x \subseteq (T \cn c_\alpha) \setminus \bigcup_{\beta \in F}(T \cn s_\beta)$. Then $f(x) \geq p$. Thus $f[X]$ is cofinal in $(\cf C \times \prod^\mathrm{w}_{\beta < \mu}\{0,1\}, \leq)$.

 Then since $G$ is closed under finite intersection and generates $\U$, \[(\U, \supseteq) \equiv_T (G, \supseteq) \equiv_T (\cf C \times \prod^\mathrm{w}_{\beta < \mu}\{0,1\}, \leq).\]
\end{proof}

From Theorem \ref{tree algebras} and Fact \ref{f: top type equiv to a prod}, we have the following corollary:

\begin{cor}\label{U top iff kappa succs of C}
Let $\kappa > \om$ and let $T$ be a tree of size $\kappa$. Then $\treealg T$ has an ultrafilter with type $\topkappa$ if and only if $T$ has an initial chain with $\kappa$-many immediate successors.
\end{cor}

From Theorem \ref{tree algebras} we can describe the Tukey spectrum of a tree algebra.

\begin{thm} \label{c.spectrum of tree algebra}
Let $T$ be a tree. The Tukey spectrum of $\treealg T$ consists of those Tukey types $(\cf C \times \prod^\mathrm{w}_{\beta < \mu}\{0,1\}, \leq)$ where $C \subseteq T$ is an initial chain with $\mu$-many immediate successors.
\end{thm}

Finally, we turn our attention to the broader class of pseudo-tree algebras.
Corollary \ref{U top iff kappa succs of C} showed that the tree algebra on an uncountable  tree $T$ has an ultrafilter of top Tukey type if and only if there is an initial chain $C$ in $T$ with $\abs{\imm(C)}=\abs{T}$.
One possible pseudo-tree analog of ``having an initial chain with $\abs{T}$-many immediate successors'' would be ``having an initial chain $C$ with $\varepsilon_C=\abs{T}$'', and so one could ask whether the ultrafilter corresponding to such an initial chain has top Tukey type. The answer is ``no''. For example, let $T$ be a linear order of order type $\omega_1 + 1 + \omega_1^*$ (this is also a pseudo-tree), and let $C$ consist of the first $\omega_1$-many elements of $T$. Then by Theorem \ref{interval algebras}, the ultrafilter corresponding to $C$ has type $(\omega_1, \leq)$, which is strictly less than the top type for $\treealg T$ by Fact \ref{facts.useful} (4).

The next Fact shows that uncountable pseudo-tree algebras always have ultrafilters whose Tukey type is strictly below the maximum type.

\begin{fact}\label{f.unctbl tree algebras have more than top type}
Let $T$ be an uncountable pseudo-tree. Then there is an ultrafilter $\U$ on $\treealg T$ whose Tukey type is strictly less than that of $([\abs{T}]^{<\omega}, \subseteq)$.
\end{fact}

\begin{proof}
Let $T$ be an uncountable pseudo-tree. Let $C$ be any initial chain such that for no $t \in T$ is $t > C$, and let $\U$ be the ultrafilter corresponding to $C$. Then $C$ is generated by $G=\{T \cn c: c \in C\}$, so that $(U, \supseteq) \equiv_T (G, \supseteq) \equiv_T (\kappa, \leq)$ for some cardinal $\kappa$. Since $T$ is uncountable, $(\kappa, \leq) \not\equiv_T ([\abs{T}]^{<\omega}, \subseteq)$.
\end{proof}

\begin{prop}\label{finite product types attained}
Let $\lambda$ be any cardinal (finite or infinite) and let $\{\kappa_\delta: \delta < \lambda\}$ be a set of
regular
cardinals, each of which is either infinite or else $2$.
Then there is a pseudo-tree $T$ and an ultrafilter $\U$ on $\treealg T$ such that $(\U, \supseteq) \equiv_T \prod^{\mathrm{w}}_{\delta < \lambda} \kappa_\delta$.
\end{prop}

\begin{proof}
Let
 regular
cardinals $\kappa_\delta$, for $\delta < \lambda$, be given, where each $\kappa_{\delta}$ is either infinite or else $2$.
For each $\delta<\lambda$,
let $\kappa'_\delta=\kappa_\delta$ if $\kappa_\delta$ is an infinite cardinal, and let $\kappa'_\delta=1$ if $\kappa_\delta=2$.
Let $T$ be the pseudo-tree constructed by putting above a single root $r$ $\lambda$-many pairwise-incomparable linear orders $T_\delta=\{t^\delta_\alpha: \alpha < \kappa'_\delta\}$ where each $T_\delta$ is an inverted copy of $\kappa'_\delta$ -- that is, $T_\delta$ is isomorphic to $(\kappa'_\delta)^*$.
 Let $A=\treealg T$ be the pseudo-tree algebra on $T$. Let $C=\{r\}$ and let $\U$ be the ultrafilter associated with $C$.
Then $\U=\langle G \rangle$ where \[G=\{(T \cn r) \setminus \bigcup_{s \in S}(T \cn s): S \textrm{ is a finite antichain of elements above } r\}.\]
Since any such antichain $S$ consists of at most one element $t^\delta_{\alpha_\delta}$ from each $T_\delta$, for $\delta < \lambda$, a typical element of $G$ is of the form
$(T \cn r) \setminus \bigcup_{\delta\in F}(T \cn t^{\delta}_{\alpha_{\delta}})$ for some  $F\in [\lambda]^{<\om}$ and  $\alpha_{\delta}<\kappa'_{\delta}$, $\delta\in F$.
Also note that $(G, \supseteq) \equiv_T (\U, \supseteq)$, since $G$ is cofinal in $\U$.

Define $f \colon (G, \supseteq) \to (\prod^{\mathrm{w}}_{\delta < \lambda}\kappa_\delta, \leq)$ by \[f\left( (T \cn r) \setminus \bigcup_{\delta\in F}(T \cn t^{\delta}_{\alpha_{\delta}}) \right)=\langle \beta_\delta: \delta < \lambda \rangle\] where, for $\delta < \lambda$,
\[
\beta_\delta = \begin{cases}
0 & \textrm{ if } \delta \not\in F\\
1+\alpha_{\delta} & \textrm{ if } \delta \in F
\end{cases}
\]
(That is:\ in those coordinates where no part of the chain $T_\delta$ has been excluded, let  $\beta_\delta=0$; and in those coordinates where $T_\delta$ has been cut-off at $t^{\delta}_{\alpha_{\delta}}$, let $\beta_\delta=1+\alpha_{\delta}$.)
Then $f$ is a bijection between $(G, \supseteq)$ and  $(\prod^{\mathrm{w}}_{\delta < \lambda}\kappa_\delta, \leq)$ such that for all $g,g'\in G$, $g\le g'\lra f(g)\le f(g')$.
By Fact \ref{fact.mono} (2),
 $(\U, \supseteq) \equiv_T (G, {\supseteq}) \equiv_T (\prod^{\mathrm{w}}_{\delta < \lambda}\kappa_\delta, \leq)$.
\end{proof}

The following Lemma \ref{lem.lambdafan} distills the essential structure inside any set of approximate immediate successors above a chain in a pseudo-tree.
This structure is given by the following notion of a $\lambda$-fan.

\begin{defn}\label{def.lambdafan}
Let   $C$ be an initial chain in a pseudo-tree $T$.
A set $\Lambda=\{t^\alpha_\beta: \alpha < \lambda, \beta < \theta_\alpha\}$   of elements of $T$ above $C$
  is a \textit{$\lambda$-fan above $C$} if  the following four conditions hold:
\begin{enumerate}
\item
$\Lambda$ is a set of approximate immediate successors of $C$.
\item
$\lambda$ is a cardinal and for each $\alpha<\lambda$, $\theta_\alpha$ is either equal to $1$ or an infinite regular cardinal.
\item
For each $\al<\lambda$,
$\{t^\alpha_\beta:  \beta < \theta_\alpha\}$
 is a strictly decreasing coinitial chain  above $C$.
\item
For $\alpha < \alpha' < \lambda$, $\beta < \theta_\alpha$, and $\beta' < \theta_{\alpha'}$, $t^\alpha_\beta \perp t^{\alpha'}_{\beta'}$.
\end{enumerate}
\end{defn}

\begin{lem}\label{lem.lambdafan}
Let $T$ be a pseudo-tree and  let $C$ be an initial chain in $T$.
Given any set $S$ of approximate immediate successors of $C$,
there is a $\lambda$-fan $\Lambda=\{t^{\al}_{\beta}: \al<\lambda, \beta<\theta_{\al}\}$ above $C$ which is coinitial in $S$.
Moreover, the cardinal $\lambda$ and set of cardinals $\{\theta_{\al}:\al<\lambda\}$ are uniquely determined by $C$.
\end{lem}

\begin{proof}
Let $T$ be a pseudotree and let
 $C$ be an initial chain in $T$.
Let $S\sse T$ be a set of approximate immediate successors of $C$ of minimal cardinality.
Let $\kappa=|S|$, and enumerate the members of $S$ as $s_{\delta}$, for $\delta<\kappa$.
For each $\delta<\kappa$,
let $\gamma(\delta)$ be the least $\gamma<\kappa$ such that
$((T \bl s_{\gamma}) \setminus C)\cap((T \bl s_\delta) \setminus C)\ne\emptyset$.
Note that $\gamma(\delta)\le\delta$.
Observe that
each $(T \bl s_\delta) \setminus C$ is ``closed downwards above $C$'' -- that is, if $t \in (T \bl s_\delta) \setminus C$ and $C < s \leq t$, then $s \in (T \bl s_\delta) \setminus C$.

\begin{subclaim} $((T \bl s_\delta)\setminus C)\cap((T \bl s_\eta)\setminus C)\ne \emptyset$
if and only if $\gamma(\delta)=\gamma(\eta)$.
\end{subclaim}

\begin{proof}
 First suppose $((T \bl s_\delta)\setminus C)\cap((T \bl s_\eta)\setminus C)\ne \emptyset$. Since also $((T \bl s_\delta)\setminus C)\cap((T \bl s_{\gamma(\delta)})\setminus C)\ne \emptyset$ and all of these sets are downwards-closed linear orders above $C$, we have $((T \bl s_\eta)\setminus C)\cap((T \bl s_{\gamma(\delta)})\setminus C)\ne \emptyset$. Then $\gamma(\eta) \leq \gamma(\delta)$ by minimality of $\gamma(\eta)$. Similarly $\gamma(\delta) \leq \gamma(\eta)$.

Now suppose that $\gamma(\delta) = \gamma(\eta)$. Then $((T \bl s_\delta)\setminus C)\cap((T \bl s_{\gamma(\delta)})\setminus C)\ne \emptyset$ and $((T \bl s_\eta)\setminus C)\cap((T \bl s_{\gamma(\delta)})\setminus C)\ne \emptyset$. It follows that $((T \bl s_\delta)\setminus C)\cap((T \bl s_\eta)\setminus C)\ne \emptyset$.
\end{proof}

By Subclaim 1,  $(T \bl s_\delta) \setminus C$ and $(T \bl s_\eta) \setminus C$ are disjoint if and only if
$\gamma(\delta)\ne\gamma(\eta)$.
Let $\lambda$ be the cardinality of the set $\{\gamma(\delta):\delta<\kappa\}$, and enumerate the set $\{s_{\gamma(\delta)}:\delta<\kappa\}$ as $\{t^\al_0:\al<\lambda\}$.
For each $\al<\lambda$, let $\theta_{\al}$ be the coinitiality of $(T \bl t^{\al}_0) \setminus C$, and let $\{t^\al_\beta:  \beta < \theta_\al\}$ be a decreasing coinitial sequence in $(T \bl t^\al_0)\setminus C$.
It follows that  (2) - (4) in the definition of a $\lambda$-fan hold.

\begin{subclaim}
Let $\Lambda=\{t^\al_\beta: \al< \lambda, \beta < \theta_\al\}$. Then $\Lambda$ is a set of approximate immediate successors of $C$.
\end{subclaim}

\begin{proof}
  First note that $C < \Lambda$. Suppose $r>C$. As $S$ is a set of approximate immediate successors of $C$, there is an $s_\delta \in S$ with $C < s_\delta \leq r$.
We have $((T \bl s_\delta) \setminus C) \cap ((T \bl s_{\gamma(\delta)}) \setminus C) \neq \emptyset$.
Say $s_{\gamma(\delta)}=t_0^{\delta}$ for some $\delta < \lambda$.
Pick $\beta$ large enough so that $t^\al_\beta \in  ((T \bl s_\delta) \setminus C) \cap ((T \bl s_{\gamma(\delta)}) \setminus C)$.
Then $t^\al_\beta \in \Lambda$ and $C < t^\al_\beta \leq s_\delta \leq r$. Thus $\Lambda$ is a set of approximate immediate successors of $C$; hence, Subclaim 2 holds.
\end{proof}

Thus, (1) in the definition of $\lambda$-fan holds, so  $\Lambda$ is a $\lambda$-fan above $C$.

Now suppose $S'$ is another set of approximate immediate successors of $C$  and that  $\Lambda'=\{u^{\xi}_{\zeta}:\xi<\lambda',\ \zeta<\theta'_{\xi}\}\sse S'$ is
 a $\lambda'$-fan  above $C$.
For each $\al<\lambda$, let $S_{\al}$ denote $\{t^{\al}_{\beta}:\beta<\theta_{\al}\}$ and for each $\xi<\lambda'$, let $S'_{\xi}$ denote $\{u^{\xi}_{\zeta}:\zeta<\theta'_{\xi}\}$.
Let $\overline{S}_{\al}$ denote $\{t\in T: t>C $ and $\exists \beta<\theta_{\al}(t\le t^{\al}_{\beta})\}$,
and  $\overline{S}_{\xi}'$ denote  $\{t\in T: t>C $ and $\exists \zeta<\theta_{\xi}'(t\le u^{\xi}_{\zeta})\}$.
For each $\al<\lambda$, there is a $\xi(\al)<\lambda'$ and a $\zeta(\al)<\theta'_{\xi(\al)}$ such that $u^{\xi(\al)}_{\zeta(\al)}\le t^{\al}_0$.
Thus,
 $\overline{S}_{\al}$ and $\overline{S}_{\xi(\al)}'$
have a common coinitial segment above $C$.
By property (4) of a $\lambda$-fan,
for all $\xi'\ne\xi(\al)$,
$\overline{S}'_{\xi'}\cap\overline{S}'_{\xi(\al)}=\emptyset$.
Therefore,
this  $\xi(\al)$ is unique.
Define $\varphi(\al)$ to be this $\xi(\al)$.
This defines  a one-to-one function $\varphi:\lambda\ra\lambda'$.
Since for each $\xi<\lambda'$ there is an $\al(\xi)<\lambda$ and a $\beta(\xi)$ such that $t^{\al(\xi)}_{\beta(\xi)}\le u^{\xi}_0$,
a similar argument reveals that
the function $\varphi$ is also onto $\lambda'$.
Thus, $\varphi$ is a bijection; hence $\lambda=\lambda'$.
As noted above, for each $\al<\lambda$,
$\overline{S}_{\al}$ and $\overline{S}_{\varphi(\al)}'$
have a common coinitial segment above $C$.
The coinitiality of this segment must simultaneously be equal to $\theta_{\al}$ and $\theta'_{\varphi(\al)}$.
Hence, $\theta'_{\varphi(\al)}=\theta_{\al}$.
Therefore, the cardinals representing any $\lambda$-fan above $C$ are uniquely determined by $C$.
\end{proof}

The previous lemma is now applied to characterize the Tukey types of ultrafilters on  pseudo-tree algebras.

\begin{thm}\label{Tukey types of ults on pseudo-tree algebras}
Let $T$ be a pseudo-tree and let $\U$ be an ultrafilter on $\treealg T$.
Then $\U$ is Tukey equivalent to $(\mu\times\prod^{\mathrm{w}}_{\al < \lambda}\kappa_\al, \leq)$,
where
$\mu$ is either $1$ or an infinite regular cardinal,
$\lambda$ is some cardinal, and for $\al<\lambda$, $\kappa_\al$ is either $2$ or else an infinite regular cardinal.
\end{thm}

\begin{proof}
Let $T$ be a pseudotree and let $\mathcal{U}$ an ultrafilter on $\treealg T$.
Let $C=\phi(\U)$ be the initial chain corresponding to $\mathcal{U}$ and let $S\sse T$ be a set of approximate immediate successors of $C$ of minimal cardinality.
By Lemma
\ref{lem.lambdafan},
there is a coinitial subset $\Lambda\sse S$ which is a
  $\lambda$-fan above $C$ of the form $\{t^{\al}_{\beta}:\al<\lambda,\ \beta<\theta_{\al}\}$
which is coinitial in $S$,  where $\lambda$ is a cardinal, each $\theta_{\al}$ is either $1$ or  an infinite regular cardinal, and these cardinals are uniquely determined by $C$.
For each $\al<\lambda$, let $\kappa_{\al}=1 +\theta_{\al}$.
Shifting the lower indices of the members of $\Lambda$ by one and letting $s^{\al}_{1+\beta}=t^{\al}_{\beta}$,
we re-write  $\Lambda$ as $\{s^{\al}_\beta:\al<\lambda$, $1\le\beta<\kappa_{\al}\}$.

Let $\mu=\cf C$, and let
$\{c_\xi: \xi < \mu\}$ be an increasing cofinal sequence in $C$.
Then  $\U=\langle G \rangle$ where
\[G=\{(T \cn c_\xi)\setminus \bigcup_{s \in F}(T \cn s): \xi < \mu \textrm{ and $F$ is a finite antichain in $\Lambda$}\},\]
since $\Lambda$ is a set of approximate immediate successors of $C$.
We claim that $(G, \supseteq) \equiv_T (\mu \times \prod^{\mathrm{w}}_{\al < \lambda}\kappa_\al, \leq)$.
Define a map $f \colon G \to \mu \times \prod^{\mathrm{w}}_{\al < \lambda}\kappa_\al$ by
$f((T \cn c_\xi)\setminus \bigcup_{s \in F}(T \cn s)) = \langle \xi \rangle^{\smallfrown} \langle \varepsilon_\al: \al < \lambda \rangle$, where for $\al<\lambda$,
\[
\varepsilon_\al = \begin{cases}
0, \textrm{ if } s^\al_\beta \not\in F \textrm{ for all }1 \leq \beta < \kappa_\al\\
\beta, \textrm{ if } s^\al_\beta \in F \textrm{ for some }1 \leq \beta < \kappa_\al.
\end{cases}
\]
Note that $f$ is a bijection which preserves order both ways; that is,  for $g,g'\in G$, $g\le g'\lra f(g)\le f(g')$.
Thus $(\U, \subseteq) \equiv_T (G, \supseteq) \equiv_T \mu \times \prod^{\mathrm{w}}_{\al < \lambda}\kappa_\al$,
by Fact \ref{fact.mono} (2).
\end{proof}

Note that this is consistent with what we already know about ultrafilters on tree algebras from Corollary \ref{U top iff kappa succs of C}, because for any $\kappa$, $\topkappa \equiv_T \prod^{\mathrm{w}}_{\alpha < \kappa} \{0,1\}$.

Since by Lemma \ref{lem.lambdafan},  every set of approximate immediate successors of an initial chain $C$ has, up to isomorphism, the same $\lambda$-fan,
we shall speak of {\em the} $\lambda$-fan above $C$.
The characterization of the Tukey spectra of pseudo-trees  follows immediately from
Lemma \ref{lem.lambdafan} and
Theorem \ref{Tukey types of ults on pseudo-tree algebras}.
Further, combined with Fact \ref{facts.useful} (2), they tell us exactly when a pseudo-tree has an ultrafilter with maximum Tukey type.

\begin{thm}\label{p.when pseudo-tree algebras have top type ult}
Let $T$ be a pseudo-tree with a single root. The Tukey spectrum of $\treealg T$ consists of exactly those types $(\cf C \times \prod^{\mathrm{w}}_{\alpha < \lambda}\kappa_\alpha, \leq)$,
 where $C$ is an initial chain with  $\lambda$-fan  of approximate immediate successors  $\Lambda=\{s^\alpha_\beta: \alpha < \lambda, \beta < \theta_\alpha\}$
and $\kappa_{\alpha}=1+\theta_{\alpha}$.

If $\abs{T}=\kappa$, then $T$ has an ultrafilter with maximal type $([\kappa]^{< \omega}, \subseteq)$ if and only if there is an initial chain $C \subseteq T$
with a $\kappa$-fan $K=\{s^\alpha_\beta: \alpha < \kappa, \beta < \theta_\alpha\}$ of approximate immediate successors above $C$,  where $\kappa$-many of the cardinals $\theta_\alpha$ are 1.
\end{thm}

\begin{rem}
We point out that $\cf C \times \prod^{\mathrm{w}}_{\alpha < \lambda}\kappa_\alpha$ is really the same as $\prod^{\mathrm{w}}_{\alpha < \lambda+1}\kappa_\alpha$,
where we define $\kappa_{\lambda}$ to be $\cf C$.
We leave the $\cf C$ on the left to remind the reader of how the structure of the pseudo-tree influences the Tukey types of its ultrafilters.
\end{rem}

\section{Questions}\label{sec.Questions}

We conclude with some open  questions either motivating or arising from this paper.

\begin{question}\label{q.WhichHaveTop}
Characterize those Boolean algebras that have an ultrafilter of the maximum  Tukey type, and characterize those Boolean algebras that have an  ultrafilter of  Tukey type strictly
below the maximum.
\end{question}

\begin{question}\label{q.charfree}
If $\bB$ is an infinite  Boolean algebra  such  that all ultrafilters  on $\bB$ have maximum Tukey type, is $\bB$ necessarily a free algebra?
\end{question}

Or is the following possible?

\begin{question}\label{q.TscFreealg}
Does the completion of a free Boolean algebra  have only  ultrafilters which are of maximum Tukey type?
\end{question}

If not, can we at least rule out the remaining possible case of a  cofinally scalene ultrafilter?

\begin{question}\label{q.CohenAlg}
Can the completion of a free Boolean algebra have an ultrafilter which is cofinally scalene; that is Tukey equivalent to $\prod_{\al<\lambda}\kappa_{\al}$, for some infinite $\lambda$ and each $\kappa_{\al}\ge \om$?
In particular, can the Cohen algebra have an ultrafilter Tukey equivalent to $(\om^{\om},\le)$?
\end{question}

Note that a positive answer to Question \ref{q.CohenAlg} would imply a negative answer to Question \ref{q.TscFreealg}, and a positive answer to Question \ref{q.TscFreealg} would imply a negative answer to Question \ref{q.charfree}.

\begin{question}\label{q.Superatomic}
What are the Tukey spectra of superatomic Boolean algebras?
\end{question}

\section{Bibliography}

\bibliographystyle{spmpsci}
\bibliography{references}

\end{document}

config: arxiv