Does the lattice of power-of-two-aligned subsets have a name?

36 Views Asked by At

The subsets of $\mathbb Z$ of the form $$ [a\cdot 2^n,…, (a+1)\cdot2^n-1] \text{ where } a \in \mathbb Z, \, n \ge 0 $$ have a nice structure as a semi-lattice: For example two such sets are either completely disjoint, or one is a subset of the other (is there a name for that?).

For a software verification project, I am in the process of formalizing this theory in the theorem prover Coq, so I need to name these.

Do these sets, of the lattice of these sets, have a common name?

1

There are 1 best solutions below

0
On BEST ANSWER

The sets themselves are dyadic intervals of integers.

I don't know a name for that particular lattice, but one perspective is that it is the lattice of closed balls in the ultrametric on $\mathbb Z$ defined by $d(a,b)=2^n$ for $a\neq b$ where $n$ is the largest integer such that $\lfloor a/2^n\rfloor=\lfloor b/2^n\rfloor,$ with $d(a,b)=\infty$ if $a<0$ and $b\geq 0$ or vice versa. In phylogenetics, the lattice would be called the ultrametric tree, for this ultrametric.