37
votes
Accepted
What is the name of this combinatorial object and place to read about it?
What you're asking for is a code with two non-usual restrictions. It's a code over alphabet size $d$. You want each code word to have length $pd$ and you want to have $qd$ total code words.
The ...
29
votes
Is there a Kolmogorov complexity proof of the prime number theorem?
Firstly, the proof given there doesn't really show that $p_n = O(n(\log n)^2)$
(at least not without further effort). Instead what it shows is that there are
$n$ for which $p_n = O(n(\log n)^2)$, ...
24
votes
Accepted
Hamming distance to primes
See OEIS sequences A067760 and A076336. If $n$ is a dual Sierpiński number, there is no $k$ such that $n+2^k$ is prime. There is no prime with Hamming distance $1$ to the Sierpiński number $2131099$, ...
22
votes
Accepted
Maximal set of $n$-bit strings that does not span $\mathbb{R}^n$
If $S$ contains more than $2^{n-1}$ strings, then by pigeonhole principle for every $j=1,2,\ldots, n$ it contains two strings which differ only at $j$-th coordinate. The difference of these two ...
12
votes
Accepted
When can this condition on linear codes be satisfied?
Any maximal $r$-separated set is an $r$-net, otherwise you can augment it with a non-covered point.
But the same holds for linear codes! If a subspace $V$ is $r$-separated but not an $r$-net, you may ...
11
votes
How did they come up with the MRRW bound?
For linear programming type bounds it is sometimes only possible to give effective bounds (that is bounds that work and are manageable) and what is surprising is that the primitive method often gives ...
11
votes
Accepted
Bipartite version of Hamming bound (two families of codewords with large Hamming distance)?
If the Hamming distance between $A$ and $B$ is at least $d$, it yields that $B$ is disjoint from the $(d-1)$-neighborhood of $A$. By isoperimetric inequality for a Boolean cube (Harper's theorem), the ...
9
votes
Accepted
Is primality essential in Varshamov's bound?
The analogue of the Varshamov inequality need not hold for instance for $\lvert\Sigma\rvert=q=6$: For $n=4$ and $d=3$ it would give a code $C\subseteq\Sigma^4$ with $d(C)\ge3$ and $\lvert C\rvert=36$. ...
9
votes
Characterization of metrics such that the volume of balls doesn't depend on their centers?
I do not know the answer in general, but in the case in which $X$ is a subset of $\mathbb{R}^n$ there are some known remarkable results:
If $X\subset\mathbb{R}^2$ is bounded, then $X$ consists of ...
9
votes
The chromatic number of the union of two graphs
This is a comment, not an answer, but it will be more convenient to post it as an answer. Consider the vertices of $G_n$ as subsets of $[n]=\{1,\dots,n\}$.
Observation 1. $\chi(G_n)\ge\left\lfloor\...
9
votes
Accepted
What are bit strings where all non-trivial rotations match at a minimum number of places called?
Gold codes are not really what you are looking for as far as I understand. With Gold codes you have many sequences and you want to control (i.e., have small absolute values) for all nontrivial auto ...
8
votes
Is there a Kolmogorov complexity proof of the prime number theorem?
I think it’s not uncommon for arguments in elementary number theory to be “philosophically” information-theoretic in nature. But this is not a very deep fact - at the end of the day it all comes down ...
8
votes
The chromatic number of the union of two graphs
In a similar vein to $\chi^{\ast}(G_n)$, we can define a quantity $\chi^{\ast \ast}(G_n)$ as follows: Suppose you have an abelian group $M$ and a set $S=\{x_1, x_2, \dots, x_n\}\subset M$, such that ...
8
votes
What do we know about the $\mathbb{F}_{q^2}$-curve $X^{q-1} + Y^{q-1} + Z^{q-1}$?
In Rational points on some Fermat curves and surfaces over finite fields, Voloch and Zieve study such curves and their points with coordinates in $\mathbb{F}_{q^i}$ for $i\le3$.
7
votes
Accepted
Codes with a twisted cyclic action
This is an extended comment that may be too long for the comment section.
If I understand your question correctly, the linear codes you described are automatically trivial.
Define $\pi_{c}$ to be ...
7
votes
Maximal set of $n$-bit strings that does not span $\mathbb{R}^n$
Assume that $S$ does not span $\mathbb{R}^n$. As $S$ is a subset of $\mathbb{Q}^n$, it does not span $\mathbb{Q}^n$ over $\mathbb{Q}$, hence there is a primitive vector $\mathbb{v}\in\mathbb{Z}^n$ ...
6
votes
Accepted
Need help with paper written in Russian... Yorgov's paper on self-dual codes with automorphisms of odd order
According to MathSciNet, a translated version of the paper is available in the journal Problems of Information Transmission ISSN: 0032-9460. Your local librarian should be able to help you track down ...
6
votes
Accepted
An isoperimetric problem on the hypercube
When A consists of even vectors only, the problem was probably solved by Korner and Wei [Odd and even Hamming spheres also have minimum boundary, Discrete Math. 51 (1984), 147–165]. See also Lemma 1....
6
votes
Accepted
How to quantify the error correction capacity of LDPC code?
It is a difficult problem to find the minimum distance of an LDPC. Vardy shows in The Intractability of Computing the Minimum Distance of a Code that it is NP-hard to find the minimum distance. ...
6
votes
Application of simple Lie algebras over finite fields
Fourier transform of invariant functions on finite reductive Lie algebras have been developed in here: http://www.springer.com/de/book/9783540240204
This can be considered the Lie algebra analogue of ...
6
votes
Accepted
Enumeration of field generators of a finite field over $\mathbb{F}_{q}$, which are $m^{th}$ powers in the same field
$$| S \cap S^m | = \sum_{n|d} \mu(n)
\frac{ \gcd ( m (q^{d/n}-1), q^{d}-1 )}{ \gcd (q^{d} - 1, m) } $$
First note that $|S \cap S^m | = |S \cap \mathbb F_{q^d}^m |$ because every $m$th power that ...
6
votes
Accepted
Guessing the number of other $1$'s in a binary sequence
Since every person knows his assigned digit, the problem is equivalent to guessing the sum of all digits.
Label the persons with $0,1,...,n$. Let person $0$ guess $0$ when given a $0$, and $n+1$ when ...
6
votes
Accepted
Existence of a joint distribution on Bernoulli variables with same probability of being pairwise different
$\newcommand{\R}{\mathbb R}\renewcommand{\le}{\leqslant}\renewcommand{\ge}{\geqslant}$Let $n:=m\ge2$.
We will show that the desired condition holds if and only if
$$p\ge\frac{\lceil n/2\rceil-1}{2 \...
6
votes
Accepted
One question on circulant $\pm1$ matrices
This is a question about a sequence $a(t)\in \{\pm 1\}$ of period $n$ with 2 level periodic autocorrelations, with the nontrivial autocorrelations identically equal to 1. All these problems have a ...
5
votes
How to quantify the error correction capacity of LDPC code?
As @John mentioned, there is not general way and nice formula for computing the minimum distance of codes. The problem remain difficult for LDPC codes as like as other codes. But, there are several ...
5
votes
The chromatic number of a Hamming-related graph
This is pretty late, but there is a result by Frankl and Rodl (Theorem 1.11 from http://www.renyi.hu/~pfrankl/1987-3.pdf) that shows that the graph on $\mathbb{F}_2^n$ (for $n$ a multiple of four) ...
5
votes
Minimal number of n/2-subsets of [n] that contains every d-subset
By counting, you need at least $\binom{n}{d}/\binom{n/2}{d}$ different $n/2$-subsets. By the main estimate in this blog post, this is at least $\frac{1}{4}\cdot2^d$ when $d\leq\sqrt{n/2}$.
In the ...
5
votes
Minimal number of n/2-subsets of [n] that contains every d-subset
Choose $N$ $n/2$-sets at random (repetitions allowed). The probability that a given $d$-set $T$ is not covered by them equals $$p=\left(1-\frac{\binom{n-d}{n/2-d}}{\binom{n}{n/2}}\right)^N\leqslant \...
5
votes
Application of simple Lie algebras over finite fields
I apologize for the self-promotion, but this is by the request of the OP. Below are several references. I should say that they are applications for pro-$p$ groups. So I cannot think about examples for ...
5
votes
Why the dimension of bch code is unknown?
This is a problem that coding theorists have been considering since the late 1950's, both for BCH, and more generally for cyclic codes.
The problem is combinatorial in nature, tightly bound to ...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
coding-theory × 289co.combinatorics × 116
it.information-theory × 83
linear-algebra × 30
finite-fields × 30
graph-theory × 23
reference-request × 19
pr.probability × 17
ag.algebraic-geometry × 12
nt.number-theory × 12
discrete-geometry × 12
polynomials × 11
lattices × 11
matrices × 9
mg.metric-geometry × 8
algorithms × 8
computational-complexity × 8
computer-science × 8
cryptography × 8
gr.group-theory × 6
rt.representation-theory × 5
additive-combinatorics × 5
combinatorial-designs × 5
sphere-packing × 5
hamming-distance × 5