All Questions
Tagged with lattices co.combinatorics
67 questions
1
vote
0
answers
51
views
Coarse-graining a hypergraph
$\DeclareMathOperator{\poly}{\mathrm{poly}}$I have asked this question on math.SE here, but couldn't get a satisfactory answer. I have also asked a related question on math overflow here, but haven't ...
- 277
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 ...
- 1,446
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 ...
- 4,219
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. ...
- 47.3k
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 ...
- 4,713
1
vote
1
answer
111
views
Existence of some lattice path connecting all given lattice paths
My daily work concerns analysis on metric spaces and some time ago it turned out that the problem I am dealing with boils down to a certain combinatorial problem. I've checked a lot of examples and it ...
- 23.7k
1
vote
0
answers
68
views
Finding a particular kind of basis of subgroup of a lattice generated by non-negative part
For $\mathbf v=(v_1,\ldots,v_n)\in \mathbb Z^n$, let $\operatorname{supp}(\mathbf v):=\{j: v_j \ne 0\}$. For a subset $X$ of $\mathbb Z^n$, define $\operatorname{supp}(X):=\bigcup_{\mathbf v \in X} \...
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 ...
CommunityBot
- 1
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
0
votes
0
answers
110
views
Optimal covering trails in 3 and 4 dimensions
A couple of years ago, I constructively solved (inside the $AABB$ $[0,3]$ X $[0,3]$ X ... X $[0,3]$) the $k$-dimensional generalization of the infamous Nine-Dot Problem by S. Loyd (see Cyclopedia of ...
- 63.9k
1
vote
1
answer
144
views
On parametrization of a type of unimodular $2\times2$ integral matrix
A matrix $\begin{bmatrix}w&x\\y&z\end{bmatrix}\in\mathbb Z^{2\times 2}$ is unimodular if $$|wz-xy|=1$$ holds.
Is there a parametrization of such matrices with $|w||z|-xy=1$
$$w,z<0<\max(...
- 2,224
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 ...
- 60.5k
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 $...
CommunityBot
- 1
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" ...
- 7,226
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 ...
- 60.5k
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
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
1
vote
1
answer
172
views
Minimal volume of fundamental domains of lattices
Consider a full rank integer lattice in $\mathbb{R}^n$. Let $v_1$ be the shortest non-zero vector in the lattice, $v_2$ be the shortest one among those not parallel to $v_1$, $v_3$ be the shortest one ...
CommunityBot
- 1
1
vote
0
answers
124
views
Number of lattice points in a structural symmetric convex body
Let $f$ is a convex symmetric function on the interval $[-a,a]$, i.e., $f(-x)=f(x)$ for $\forall \, x\in [-a,a]$. Then we consider a $n$-dimensional convex body in Euclidean space
\begin{equation}
\...
- 13.9k
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
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 ...
CommunityBot
- 1
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 ...
- 2,175
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 ...
CommunityBot
- 1
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$...
- 2,339
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
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$ ...
- 10.4k
1
vote
1
answer
371
views
Basis of cone lattice
I only want to know whether a construction that I use appears in literature and maybe has a name already.
Let $V$ be a $\mathbb Q$ vector space of dimension $d\in\mathbb N$.
A subset $C\subset V$ is ...
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.
$...
- 30.1k
2
votes
0
answers
211
views
Combinatorial and computational problem related to Weyl groups and the coroot lattice
Let $W$ be a Weyl group with root system $R$ and with set of positive roots $R^+$. Let $\tilde{R}^+$ be the set of $B$-cosmall roots, i.e. positive roots $\alpha$ which satisfy $\ell(s_\alpha)=2\...
- 1,066
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
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 $...
- 79.9k
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
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 ...
- 85.6k
1
vote
0
answers
229
views
Geometric interpretation of k-th power of first n natural numbers and summation using Pick's theorem
I want to know is there any interesting properties of this approach or generalization to find $S_k(n)=1^k+2^k+3^k+\cdots+n^k$ by using Pick's Theorem $S=i+\tfrac{b}{2}-1$, where $i$-number of ...
- 19
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 ...
- 151k
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 ...
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
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^{\...
CommunityBot
- 1
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 ...
- 79.9k
2
votes
0
answers
121
views
Hamming weights of special vectors
The motivation of this question comes from number theory (I add the tag number theory for this reason, in that it is possible that someone with a number-theoretic background has already thought about ...
- 21
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 ...
- 1,046
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 ...
CommunityBot
- 1
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 ...
CommunityBot
- 1
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 ...
- 5,971
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
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 ...
- 6,700
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$-...
CommunityBot
- 1
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 ...
- 1,046
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 ...
CommunityBot
- 1
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 ...
