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])
652 questions
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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)...
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 ...
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 ...
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 ...
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"...
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 ...
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 ...
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 ...
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 ...
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$ ...
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 ...
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 \...
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 ...
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 ...
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 ...
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 ...
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\|} ...
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 ...
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 ...
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 \...
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.
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 $\...
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, \...
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 ...
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}^...
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$...
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 ...
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 $\...
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 ...
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?
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 $...
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 ...
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(...
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 ...
-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 ...
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 $...
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 ...
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:
...
0
votes
2
answers
611
views
Is a lattice of convex sets distributive?
Is a lattice of convex sets in $R^2$ distributive?
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 ...
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 ...
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 ...
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 ...
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 $...