All Questions
Tagged with lattices co.combinatorics
67 questions
37
votes
2
answers
2k
views
A group-theoretic perspective on Frankl's union closed problem
Here is a group theoretic phrasing of a special case of the union closed conjecture:
Question: Given a finite group $G$, is there an element of prime power order which is contained in at most half ...
- 85.6k
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 ...
- 12.6k
16
votes
4
answers
597
views
The lattice spanned by $m$ random 0-1 vectors of length $n$
Consider $m$ random 0-1 vectors of length $n$. Let $L$ be the lattice spanned by them. What is the value of $m$ (as a function of $n$) for which it is true with positive probability that $L=Z^n$? More ...
- 24.7k
13
votes
3
answers
665
views
Conjecture regarding closest point inside a discrete ball to a line
I'm a PhD student in image processing, where I've stumbled into a problem that seems to be essentially number theory. I've hunted around online and while I've found many results on similar problems, ...
- 323
13
votes
2
answers
697
views
in search of a transformation between determinants
Motivated by this MO question. Consider the two matrices $A_n$ and $B_n$ with entries $\binom{2j}i$ and $\binom{n+1}{2j-i}$, respectively; for $1\leq i, \,j\leq n$.
I can show $\det A_n=\det B_n=2^{\...
- 43.2k
12
votes
2
answers
980
views
Higman's lemma and a manuscript of Erdős and Rado
Motivated by a problem in factorization theory, I've recently proved the following:
Theorem. If $X$ is a non-empty finite alphabet and $\mathcal W$ an infinite subset of the free semigroup, $X^\ast$...
- 10.5k
12
votes
3
answers
707
views
A "round" lattice with low kissing number?
Historically, the lattices with high density were studied intensively, e.g. E_8 lattice or Leech Lattice. However, there are situations that lattices with low kissing number are required. Specifically,...
- 139
11
votes
1
answer
442
views
Chromatic number of Voronoi diagrams of lattices
Let $L$ be a Euclidean lattice. Define a graph whose vertex set is $L$ and where two points $x,y\in L$ are declared to be adjacent whenever the cells of $x$ and $y$ in the Voronoi diagram of $L$ have ...
- 32.5k
10
votes
2
answers
496
views
Inequalities for averaging over partially ordered sets
Let's start from a classical inequality:
If $0\le a_1\le\cdots\le a_k$ and $0\le b_1\le\cdots\le b_k$ then
$(a_1+\cdots+a_k)(b_1+\cdots+b_k)\le k(a_1b_1+\cdots+a_k b_k)$.
It can be written also in ...
- 2,232
10
votes
3
answers
903
views
Positive integer combination of non-negative integer vectors
A vector of positive integer numbers with $n$ coordinates is given $a=(a_1,\ldots,a_n)$. It holds that $a_1+\cdots+a_n$ is divisible by some positive integer number $k$. I have checked many cases and ...
- 399
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 ...
- 15.4k
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:
...
- 30.5k
10
votes
0
answers
1k
views
Bound on the number of lattice points in d-dimensional ball
The following paper states that the number of lattice points in a $d$-dimensional ball of radius $R$ is $V_d R^d + O(R^\alpha)$ where $\alpha = d - 2$ and $V_d$ is the volume of the unit $d$-...
- 201
9
votes
1
answer
382
views
Why is the number of Perfect Matchings in a triangular grid equivalent to the number of Royal Paths?
The sequence A006318 at OEIS stands for the Schröder numbers.
They describes the number of lattice paths from the southwest corner $(0,0)$ of an $n\times n$ grid to the northeast corner $(n,n)$, ...
- 155
9
votes
0
answers
365
views
How to count integer lattice points close to a subspace of $\mathbb R^n$?
Consider $m$ linearly independent vectors in $n$-dimensional Euclidean space, $v_1,...,v_m \in \mathbb R^n$ where $1\leq m<n$, and let $U := {\rm span}(v_1,...,v_m)$ denote the $m$-dimensional ...
- 686
8
votes
1
answer
153
views
Are there Type III codes with small but nonzero "index"?
Recall that a Type III code of rank $r$ is a linear subspace $C \subset \mathbb F_3^r$ which is self-dual for the standard inner product. (These occur only when $r$ is divisible by $4$.) Elements of $...
- 54.6k
7
votes
2
answers
963
views
Maximal number of edges and triangular cells for n points in a triangular lattice
Consider a subset of $n$ points in an equilateral triangular lattice. Draw all the edges between nearest-neighbor points.
What is the maximum, over all such subsets, of the number of edges? This ...
- 567
7
votes
2
answers
922
views
what is the number of paths returning to 0 on the hexagonal lattice
I am looking for an estimation of the number of paths of length $n$ going from 0 to 0 on the hexagonal (or honeycomb) lattice.
I can find plenty on references on self avoiding paths, but I am looking ...
- 1,352
7
votes
1
answer
271
views
How "accidental" are equalities between parts of Ehrhart quasi-polynomials? When do they persist to Euler-Maclaurin?
Background
What I think of Ehrhart theory (http://en.wikipedia.org/wiki/Ehrhart_polynomial) asserts that if we take a lattice polytope $P$, and count the number of lattice points in the $t$th ...
- 2,372
7
votes
1
answer
1k
views
On "The Average Height of Planted Plane Trees" by Knuth, de Bruijn and Rice (1972)
I am trying to derive the classic paper in the title only by elementary means (no generating functions, no complex analysis, no Fourier analysis) although with much less precision. In short, I "only" ...
6
votes
2
answers
982
views
Decomposing polyhedral cones into "direct sums" and a polynomial
This question consists of two parts. I'm not breaking it up into two separate ones because posing the second question would essentially require me two rewrite the first one. Also, to some extent, the ...
- 3,513
6
votes
1
answer
451
views
Orthogonal Complements of Root Lattices in E_8
I have a rather stupid lattice theory question. Suppose $L$ is a root lattice that can be primitively embedded in the $ E_8 $ lattice. Is the orthogonal complement of $ L$ in $E_8$ unique up to ...
- 309
6
votes
1
answer
205
views
Preserve validity between the two Kripke frames
The background of our discussion is intuitionistic logic, i.e. the following definitions are intuitionistic Kripke frame.
For $n \geq 1$, let $\mathcal{C}_n$ denote the frame which is shown in Fig.1. ...
- 53
6
votes
1
answer
269
views
Problem with the vertices of a convex quadrilateral on integer lattice
I made the following observation and I am wondering if it is always true.
Let $x_1$, $x_2$, $x_3$ and $x_4$ be four positive integer points in the plane ($x_i\in\mathbb{Z^2_{\geq 0}}$) forming a ...
- 61
6
votes
0
answers
183
views
Root system inside the indefinite even unimodular lattice $II_{10,2}$
I apologize for asking questions that seem likely to be answered in Conway & Sloane's "Sphere Packings, Lattices, and Groups" if I knew where to look.
Let $L$ be the unique* even unimodular ...
- 27.8k
5
votes
1
answer
2k
views
Is there a relation between the number of lattice points lie within these circles
Suppose we have a circle of radius $r$ centered at the origin $(0,0)$. The number of integer lattice points within the circle, $N$, can be bounded using Gauss circle problem.
Suppose that another ...
- 225
5
votes
2
answers
635
views
Area of a lattice polygon in terms of its width
Let $M$ be a lattice polygon on a plane (i.e. its vertices are integer points $(i,j)\in\mathbb Z^2$).
Let us define lattice width in a direction $v=(m,n)\in\mathbb Z^2$ as $w_v(M)=\max\limits_{x,y\in ...
- 5,063
5
votes
1
answer
190
views
Number of distinct normalized vectors from the center of a hexagon in a hexagonal grid
Consider an infinite hexagonal grid composed of regular hexagons. Choose any hex to be the origin hex. Let n be a natural number.
Find an expression, in terms of n, for the number of distinct ...
5
votes
2
answers
398
views
Ordered lattice point enumeration
I initially asked this question over at StackOverflow as it has algorithmic flavor to it, but I haven't been getting much traction so I thought I would probe the mathematics community.
Setup: Let $e_{...
- 547
5
votes
0
answers
324
views
Lattice points inside a (n-dimensional) tetrahedron
Hi, overflowers.
I was interested in a sharp lower bound for the number of lattice points (say, integral lattice points) inside the tetrahedron defined by the coordinate hyperplanes and $x_1/a_1+...+...
- 306
4
votes
2
answers
2k
views
Can we count the number of integer lattice points in this case?
Gauss Circle problem gives the number of lattice points lie within a circle of radius $r$. This question points to a reference that estimates the number of lattice points in a $d−$dimensional ball.
$...
- 225
4
votes
2
answers
323
views
Cancellation theorem for lattices
By a lattice, we mean a finitely generated, free $\mathbb{Z}$-module together with a symmetric bilinear form. Typical examples are the hyperbolic lattices $U$ and the root lattices $A_{n}, D_{n}, E_{n}...
- 41
4
votes
2
answers
494
views
Self-dual binary codes of Hamming weight divisible by 8?
Recall that a binary code is a subgroup $C \subset \mathbb F_2^n$; the elements of $C$ are called code words. The Hamming weight of a code word $c\in C$ is the number of $1$s in it. A binary code is ...
- 54.6k
4
votes
1
answer
390
views
When does a subgroup of $\operatorname{GL}(n, \mathbb Q)$ have a bounded fundamental domain on $\mathbb R^n$?
$\DeclareMathOperator\GL{GL}$Let $G \subset M_{n\times n~}(\mathbb Z)$ be a finitely generated subgroup of $\GL(n,\mathbb Q)$ (i.e. $g\in G$ is an invertible matrix with entries in $\mathbb Z$). Then $...
- 3,472
4
votes
1
answer
293
views
Number of points in a lattice and an oblong box
I have a very simple question in geometry of numbers. (It is a slight modification of Counting points on the intersection of a box and a lattice .) There's a bound I can easily prove, and it's good ...
- 20.2k
4
votes
0
answers
222
views
Random walk on hexagonal lattice. First return to the origin
I'm trying to come up with the formula describing the number of paths on hexagonal lattice of length $2n$ that start at the origin $O$ and go back to $O$ but doing so for the first time at step $2n$ (...
- 255
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 ...
- 1,288
3
votes
2
answers
197
views
Limit of the Schröder numbers ratio
I have been playing around with interesting integer sequences and came across Schröder number which defines the number of lattice paths of n x n grid.
The recurrence formula to calculate these numbers ...
3
votes
2
answers
260
views
Number of *distinct* dot products of an integer vector by elements of a hyper-rectangle
Imagine a vector $\boldsymbol{v}$ composed of integers, and the set $S$ of all integer vectors within a hyper-rectange, with one corner at the origin and other at $\boldsymbol{m}$. In other words: $S ...
- 379
3
votes
1
answer
607
views
Automorphism groups of indefinite non-unimodular integer lattices
Does anyone know of any papers in which structural aspects of the orthogonal group of some indefinite non-unimodular integral lattice are calculated? The exact lattice isn't so important and they don'...
- 31
3
votes
0
answers
149
views
A question about smooth convex lattice polygons
Let $P$ be a smooth convex lattice polygon in $\mathbb{R}^2$ (the lattice being $\mathbb{Z}^2$). Here smooth means that at any vertex of $P$, the two primitive integer vectors (i.e. vectors whose ...
- 113
2
votes
1
answer
300
views
Spanning set for Lattice generated by an orbit of the group.
For a vector spaces it always holds that any set of vectors spanning vector space $V$ has a subset of vectors which is a basis for $V$. While for lattices it is not true. For example consider one ...
- 2,179
2
votes
1
answer
280
views
Partitioning $\{0,1\}^n$ into $n$ sets
I am working on an answer to the question
Magic trick based on deep mathematics
and came across the following problem: I am trying to partition the cube $\{0,1\}^n$ into $n$ sets $P_1,\dots,P_n$ ...
- 21
2
votes
1
answer
267
views
Expected number of identical vertex pairs with the same Euclidean distance on a randomly colored rectangular lattice
Imagine I have an $N$ by $M$ rectangular lattice where I randomly assign one of $k$ colors to every vertex in the lattice. I then write down a list of the ${N*M}\choose{2}$ possible unordered pairs ...
- 23
2
votes
1
answer
324
views
Lattice automorphisms of finite order
Are there any known examples of lattice automorphisms of finite order in indefinite lattices being classified up to conjugacy?
- 23
2
votes
2
answers
689
views
Given an integer lattice, how to count the number of points whose norm is smaller than some bound $M$?
Let $\mathbf{b}_1, \mathbf{b}_2, ..., \mathbf{b}_n$ be linearly independent $m$-dimensional vectors whose entries belong to $[0, M] \cap \mathbb{Z}$, for some $M \in \mathbb{N}^*$. Of course, $n \le ...
2
votes
1
answer
147
views
Relation to Ehrhart polynomial with Uniqueness
A set of relative prime, positive integers $A = [a_1, \dots, a_d]$ describe the restricted partition function
$$
p_A(n) = \# \{(m_1,\dots,m_d)\in\mathbb{Z}^d: \textrm{ all }m_j \geq 0, \sum_{j=1}^d ...
- 909
2
votes
1
answer
119
views
Anchor sets for lattice polygons: Part I
Suppose $V=\{(x_1,y_1), (x_2,y_2),\dots,(x_v,y_v)\}$ is a vertex set of lattice points satisfying
$$0=x_1<x_2<\dots<x_v \qquad \text{and} \qquad y_1>y_2>\cdots>y_{v-1}>y_v=0.$$
...
- 43.2k
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 ...
- 125
2
votes
0
answers
69
views
Why is Schröder numbers equivalent to the number of perfect matchings for triangular grid of n squares and how the graph look like? [duplicate]
In the OEIS entry for the Schröder numbers is A006318. There is a comment which related the sequence to perfect matchings:
The number of perfect matchings in a triangular grid of n squares (n = 1, 4, ...
- 141