Skip to main content

Questions tagged [lattices]

Lattices in the sense of discrete subgroups of Euclidean spaces, as used in number theory, discrete geometry, Lie groups, etc. (Not to be confused with lattice theory or lattices as used in physics! For lattices (ordered sets), use the tag: [lattice-theory])

Filter by
Sorted by
Tagged with
7 votes
1 answer
552 views

Integrating the multinomial over a hypercube

I have come across an integral of the form $$\int_{b}^{a}\cdots\int_{b}^{a} \left( \sum_{i=1}^{n}x_i\right)^mdx_1d x_2\dots dx_n.$$ I have a solution that makes use of the partition function, but I ...
Robby McKilliam's user avatar
2 votes
1 answer
661 views

Even lattices and binary codes

I have a maybe simple question about even positive-definite lattices and lattices coming from binary codes. They seemed to be used in framed vertex operator algebras. What is known about even ...
Marcel Bischoff's user avatar
16 votes
2 answers
2k views

How is the Ising model an example of a lattice model as per Kontsevich?

In section 3.2 of Kontsevich's very interesting paper "Notes on motives in finite characteristic,", he gives an axiomatic definition of a "lattice model" attached to a Boltzmann ...
JSE's user avatar
  • 19.2k
4 votes
2 answers
1k views

diameter of Voronoi cell of the lattice ? What about R^n ? What about small n =2,3,4 ?What about random lattice ?

Consider a lattice in R^n. Consider Voronoi cell of it. What is known about diameter ? About the shape ? What are good references ? As far as I understand they are not easy to compute. May be in ...
Alexander Chervov's user avatar
7 votes
2 answers
700 views

What groups have a second maximal subgroup below exactly four maximal subgroups?

I am looking for a finite group $G$ with the following property: there is a (core-free) subgroup $H < G$ such that the interval $\{ K : H < K < G\}$ in Sub[$G$] contains exactly four maximal ...
William DeMeo's user avatar
2 votes
2 answers
206 views

how to find vertex of parallelotope closest to given point P in R^n ? (Or minimize quadratic form over {+-1}) Is it NP ?

Consider a parallelotope in R^n and some point "P" in R^n. What algorithms (except of brute force) can be suggested to find the closest vertex of paralleloptope to "P" ? Is it NP ? Parallelotope ...
Alexander Chervov's user avatar
1 vote
0 answers
198 views

How to find closest point to restricted lattice on the plane ? ( m*h1 + n*h2, for 0<m,n<N)

Consider finite piece of lattice i.e. points of the form m*h1 + n*h2, for 0<m,n<N h1, h2 -some vectors. Consider some point "P" on the plane. How to find (m,n)...
Alexander Chervov's user avatar
9 votes
6 answers
683 views

Which finite nonabelian groups have long chains of subgroups as intervals in their subgroup lattice?

Given N, what is a finite non-abelian (and preferably non-solvable) group G in whose subgroup lattice Sub[G] there is an interval that is a chain of length at least N? Since N can be arbitrarily ...
William DeMeo's user avatar
6 votes
1 answer
2k views

Closest vector problem (=nearest lattice point) is trivial for "reduced lattice" ?

Consider some lattice in R^n. Take some point "P" in R^n (which does not belong to this lattice in general). The problem is to find "nearest" lattice point. The problem is known NP-hard in general it ...
Alexander Chervov's user avatar
12 votes
1 answer
1k views

Niemeier lattices and theta functions

I have an extremely elementary question. Let's say someone randomly hands you a theta function associated to a Niemeier lattice (unimodular even, n=24). What can you say about which Niemeier lattice ...
schur's user avatar
  • 1,022
3 votes
1 answer
407 views

How "often" does LLL-reduction produce "optimal" result ? Is there condition (or informal understanding) on lattice that it LLL is optimal ?

Consider some lattice in R^4 (C^4) or C^8. Famous "lattice reduction" procedures (like LLL latice reduction) produces some "reduced basis". However in general there results are not "the best reduced"...
Alexander Chervov's user avatar
5 votes
2 answers
979 views

Lattice reduction in R^3 (R^4) or what is fundamental domain for SL(3,Z) , (SL(4,Z)) ?

Consider a lattice in R^3. Is the some "canonical" way or ways to choose basis in it ? I mean in R^2 we can choose a basis |h_1| < |h_2| and |(h_2, h_1)| < 1/2 |h_1|. Considering lattices with ...
Alexander Chervov's user avatar
8 votes
2 answers
3k views

How to find nearest lattice point to given point in R^n ? Is it NP ?

Consider some lattice in R^n. Take some point "P" in R^n (which does not belong to this lattice in general). What are the algorithms to find some nearest lattice point to "P" ? "Nearest" - means in ...
Alexander Chervov's user avatar
1 vote
2 answers
550 views

compact elements and continuous functors

Hi, I am interested in abstracting the Scott topology from Domains to Categories. One can find a definition of a continuous functor which is just such an abstraction: A functor F:C→D is continuous ...
Ben Sprott's user avatar
  • 1,313
10 votes
2 answers
1k views

Dense sphere packings which are not lattice packings

This question is about dense sphere packings in euclidean space $\mathbb R^n$. By a sphere packing I understand any arrangement of mutually disjoint solid open spheres in $\mathbb R^n$, all of the ...
Xandi Tuni's user avatar
  • 4,015
11 votes
1 answer
3k views

Best way to find a closest vector in a lattice

Let $v_1,\dotsc,v_n$ be linearly independent vectors in $\mathbb{R}^n$, and let $\Lambda=\bigoplus_{i=1}^n \mathbb{Z}v_i$. The question is, given a vector $w$ in $\mathbb R^n$, find the element $v$ ...
David Cardon's user avatar
0 votes
0 answers
148 views

Bogus(?) proof for equivalence of normal and dual distributivity conditions in lattices

I am attempting to prove the equivalence of the following two definitions of distributive lattices: $(a \lor b) \land c = (a \land c) \lor (b \land c)$ $(a \land b) \lor c = (a \lor c) \land (b \lor ...
ezyang's user avatar
  • 101
8 votes
3 answers
2k views

Listing lattice points in a simplex

Let $n \in \mathbf{Z}_{\geq 1}$. Is there an algorithm which, given a simplex $\Delta \subset \mathbf{R}^n$ specified as the convex hull of $v_0,\dots,v_n \in \mathbf{Z}^n$, computes the set $\Delta \...
John Voight's user avatar
  • 3,009
1 vote
1 answer
268 views

Do Turing Machines generates any nontrivial lattice on the set o symbols or states?

Second question, probably better: Turing Machine which generates order on the set of its states I would like to ask ( if it is not terribly obviously wrong): Do Turing Machine generates ...
kakaz's user avatar
  • 1,626
4 votes
0 answers
242 views

Domination in Nice Lattices

Let an integer vector be nice when it has only two nonzero components, which sum to zero. So (0, 0, 3, 0, -3) and (-1, 0, 1, 0, 0) are examples of nice vectors in $n=5$ dimensions. Call a lattice ...
Dave Pritchard's user avatar
3 votes
3 answers
2k views

Lattices: why require bilinear form to be integral?

This is a quite localized question, but I hope it won't be closed as unfit to MO. Well, a lattice $\Lambda$ in $\mathbb{R}^n$ is a discrete subgroup generated by a basis. Such a lattice gets a ...
Qfwfq's user avatar
  • 23.3k
14 votes
4 answers
1k views

Localic locales? Towards very pointless spaces by iterated internalization.

One can think of locales as (generalizations of) topological spaces which don't necessary have (enough) points. Of course when one studies locales, one "actually" studies frames, certain sorts of ...
David Feldman's user avatar
5 votes
4 answers
738 views

Angles in an integral lattice

Let $d\geq 1$ be a fixed integer, and $\mathbb{Z}^d$ be the lattice of all integers; consider the set $A_d \subset [-1,1]$ defined by $$ \alpha \in A_d \ \iff \ \alpha=\frac{v \cdot w}{\|v\| \|w\|} ...
ccarminat's user avatar
  • 373
1 vote
0 answers
470 views

Complex Lorentzian Leech Lattice and the Bimonster [closed]

I'm reading an excellent paper on the complex Lorentzian Leech Lattice and the bimonster (Tathagata Basak). Instead of using the binary Golay Code, the author uses the ternary Golay code and the ...
Paul Hjelmstad's user avatar
2 votes
1 answer
337 views

Count of lattices on finite set

Let $p(n)$ denote count of lattices on finite set $G$, $|G|=n$ (without isomorphism). It's know closed formula for $p(n)$? It's clear, that $1 \leq p(n)$ and also that $p(n-1) \leq p(n)$ for $n \geq ...
tomas.lang's user avatar
3 votes
2 answers
269 views

What do you call a lattice whose meet operation preserves disjointness of subsets?

To make my question more precise and compact (and probably more intuitive), let me define the following: A subset $S$ of a lattice is mutually disjoint if for each $x \in S$, $\bigvee(S - \lbrace x \...
Tunococ's user avatar
  • 205
5 votes
1 answer
1k views

Can the Knaster-Tarski theorem be proved using the Schroeder-Bernstein theorem?

The reverse can be done easily and the proof is well known I am wondering if the exact same argument can be used to prove reverse as well.
user10122's user avatar
5 votes
1 answer
569 views

Maximum distance to nearest-lattice-point on (hyper-)sphere with unit lat-lon lattice.

Let $U$ be the set of all non-null $n \times 1$ vectors $\mathbf{\mathrm{u}}$, where $u_i \in \lbrace-1, 0, 1\rbrace$. Let $\mathbf{\mathrm{x}}$ be an $n \times 1$ vector in $\mathbf{R}^n$. Let $\...
Lee Wilkinson's user avatar
26 votes
1 answer
1k views

How random are unit lattices in number fields?

I was wondering how random unit lattices in number fields are. To make this more precise: If $K$ is a number field with embeddings $\sigma_1, \dots, \sigma_n, \overline{\sigma_{r+1}}, \dots, \...
felix's user avatar
  • 669
3 votes
0 answers
328 views

Integer relation detection for Subset Sum or NPP?

Is there a way to encode an instance of Subset Sum or the Number Partition Problem so that a (small) solution to an integer relation yields an answer? If not definitely, then in some probabilistic ...
dorkusmonkey's user avatar
0 votes
1 answer
578 views

Q-lattices and commensurability, any insight into the definition and intuition?

I've been coming across $\mathbb{Q}$-lattices in $\mathbb{R}^n$ in my reading, and I'm having trouble understanding the definitions. Connes and Marcolli define it as a lattice $\Lambda \in \mathbb{R}^...
mebassett's user avatar
33 votes
3 answers
2k views

Polar body of a convex body that avoids a lattice

Let $K \subset {\bf R}^d$ be a symmetric convex body (an open bounded convex neighbourhood of the origin with $K = -K$) with the property that $K + {\bf Z}^d \neq {\bf R}^d$, i.e. the projection of $K$...
Terry Tao's user avatar
  • 114k
7 votes
2 answers
2k views

Is there any literature on multivariable theta functions?

The theta function of a lattice is defined to be $$ \vartheta_\Lambda = \sum_{v\in\Lambda} q^{{\Vert v\Vert}^2}$$ which yields as a coefficient of qk the number of vectors of norm-squared k. On the ...
Simon Rose's user avatar
  • 6,290
4 votes
3 answers
1k views

Lattice of subcategories: subobject classifier in Cat

Two short questions: Is there any work classifying the lattice of subcategories of an arbitrary (sufficiently small) category $\mathcal{C}$, similar to the way that the set of subsets of set $\...
supercooldave's user avatar
13 votes
3 answers
1k views

When are Ehrhart functions of compact convex sets polynomials?

Given a lattice $L$ and a subset $P\subset \mathbb R^d$, we define for each positive integer $t$ $$f_P(L,t)=|(tP\cap L)|$$ the number of lattice points in $tP$. Let's say $P$ is nice if $f_P(L,t)$ is ...
Gjergji Zaimi's user avatar
1 vote
2 answers
2k views

Product lattice

Could someone explain how to construct a product lattice, or point me to an explanation on the web?
user6473's user avatar
4 votes
1 answer
403 views

Relative integral basis for CM extensions

Suppose $K=\mathbf{Q}(\sqrt{d})$; it's well known that $\mathcal{O}_K$ is $\mathbf{Z}+\frac{D+\sqrt{D}}{2}\mathbf{Z}$, where $D$ is the discriminant. What is the analogue of this for a CM extension $...
David Hansen's user avatar
  • 13.1k
1 vote
1 answer
424 views

Computing a set of coset representatives for $\mathbb{Z}^n / \Lambda$

Let $\Lambda$ be an $n$ dimensional sublattice of the integer lattice $\mathbb{Z}^n$. The quotient $\mathbb{Z}^n/\Lambda$ has order $\sqrt{\det{\Lambda}}$. What is the best/standard way to compute ...
Robby McKilliam's user avatar
7 votes
4 answers
1k views

`Topos' with alternate subobject lattice?

We know that for any topos E, and for any object A in E, the subobjects of A, Sub(A), form a Heyting lattice. Does anybody know of any sort of modification of the definition of a topos that makes Sub(...
Eric's user avatar
  • 855
4 votes
2 answers
862 views

What is a reference for the Hasse-Minkowski classification of indefinite forms?

According to "The Geometry of Four-Manifolds" by Donaldson and Kronheimer, indefinite unimodular forms are classified by their rank, signature and type. This is the Hasse-Minkowski classification of ...
Simon Rose's user avatar
  • 6,290
-2 votes
2 answers
989 views

Weak partitioning vs. strong partitioning

Let $U$ is a complete lattice with least element 0. Weak partitioning is a collection $S$ of nonempty subsets of $U$ such that $\forall x\in S: x\cap\bigcup(S\setminus\{x\})=0$. Strong partitioning ...
porton's user avatar
  • 765
2 votes
4 answers
805 views

Filter-closed vs. chain-closed

Let A is a complete lattice. I call a subset $S$ of A filter-closed when for every filter base $T$ in $S$ we have $\bigcap T\in S$. (A filter base is a nonempty, down directed set.) I call a subset $...
porton's user avatar
  • 765
0 votes
1 answer
241 views

Constructing a smooth lattice from a discrete one.

I have the standard lattice L defined over partitions of $1\ldots n$ under the split-merge relation. I also have an antimonotone function from L to R that's submodular, and so gives me a metric on L ...
Suresh Venkat's user avatar
10 votes
1 answer
595 views

Condition for existence of certain lattice points on polytopes

Let $a_1,\cdots, a_n$ be integers such that $a_i\geq 2$ for all $i$ and $k>0$ another integer. I am interested in whether there exist integers $x_1,\cdots, x_n$ with $0<x_i<a_i$ satisfying: ...
Hailong Dao's user avatar
  • 30.5k
0 votes
2 answers
611 views

Is a lattice of convex sets distributive?

Is a lattice of convex sets in $R^2$ distributive?
pyetras's user avatar
  • 11
10 votes
1 answer
803 views

Which lattices have more than one minimal periodic coloring?

The lattice $\mathbb{Z}^n$ has an essentially unique (up to permutation) minimal periodic coloring for all $n$, namely the "checkerboard" 2-coloring. Here a coloring of a lattice $L$ is a coloring of ...
Steve Huntsman's user avatar
22 votes
4 answers
2k views

What exactly is the relationship between codes over finite fields and Euclidean sphere-packings?

So I know that error-correcting codes are sphere packings in the Hamming metric, and that intuition and technical tools from the Euclidean case can often be applied to the finite-field case and vice ...
Harrison Brown's user avatar
10 votes
3 answers
644 views

Models with SLE scaling limit

What discrete processes/models have been proven to have scaling limits to $\text{SLE}(\kappa)$, for various $\kappa$? I know about loop-erased random walk and uniform spanning trees. What about ...
Gjergji Zaimi's user avatar
3 votes
1 answer
2k views

How do you construct a symplectic basis on a lattice?

Is this possible to do constructively? The only sources that I have for the possibility of this construction is an exercise in Lang's Algebra (on p. 598, I believe) which states that one can be ...
Simon Rose's user avatar
  • 6,290
12 votes
4 answers
3k views

Elliptic Curves, Lattices, Lie Algebras

I've recently started to look at elliptic curves and have three basic questions: Is it correct to say that elliptic curves $E$ in the projective plane are in bijective correspondence with lattices $...
John McCarthy's user avatar