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 ...
Pat Devlin's user avatar
  • 2,660
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)$, ...
Lucia's user avatar
  • 43.3k
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$, ...
Robert Israel's user avatar
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 ...
Fedor Petrov's user avatar
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 ...
Ilya Bogdanov's user avatar
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 ...
Josiah Park's user avatar
  • 3,177
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 ...
Fedor Petrov's user avatar
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$. ...
Peter Mueller's user avatar
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 ...
Piotr Hajlasz's user avatar
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\...
bof's user avatar
  • 11.5k
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 ...
kodlu's user avatar
  • 10.1k
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 ...
Dan Romik's user avatar
  • 2,480
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 ...
Gjergji Zaimi's user avatar
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$.
Peter Mueller's user avatar
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 ...
Yuichiro Fujiwara's user avatar
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$ ...
GH from MO's user avatar
  • 98.2k
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 ...
Willie Wong's user avatar
  • 37.4k
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....
Tuan Tran's user avatar
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. ...
John Machacek's user avatar
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 ...
Tamas Hausel's user avatar
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 ...
Will Sawin's user avatar
  • 135k
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 ...
LeechLattice's user avatar
  • 9,421
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 \...
Iosif Pinelis's user avatar
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 ...
kodlu's user avatar
  • 10.1k
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 ...
Shahrooz's user avatar
  • 4,746
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) ...
David Roberson's user avatar
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 ...
Dustin G. Mixon's user avatar
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 \...
Fedor Petrov's user avatar
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 ...
Yiftach Barnea's user avatar
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 ...
kodlu's user avatar
  • 10.1k

Only top scored, non community-wiki answers of a minimum length are eligible