**32**

votes

**1**answer

602 views

### What measurable quantity can constrain the number of odors human can discriminate?

This is not a very typical MO question, but I hope you bear with me. It concerns a recent disagreement in the biology literature about how many different odors humans can discriminate. The authors of ...

**30**

votes

**1**answer

2k views

### “The Two Sheriffs” puzzle

This puzzle is taken from the book Mathematical puzzles: a connoisseur's collection by P. Winkler.
Two sheriffs in neighboring towns are on the track of a killer, in a
case involving eight ...

**21**

votes

**2**answers

1k views

### What is the complexity of this problem?

Recently on Dick Lipton and Ken Regan's blog there was a post about problems of intermediate complexity, that is, NP problems that are harder than P but easier than NP-complete. The main message of ...

**17**

votes

**1**answer

821 views

### Codes, lattices, vertex operator algebras

At the end of "Notes on Chapter 1" in the Preface to the Third Edition of Sphere packings, lattices and groups, Conway and Sloane write the following:
Finally, we cannot resist calling attention ...

**15**

votes

**3**answers

902 views

### Can you cover the Boolean cube {0,1}^n with O(1) Hamming-balls each of radius n/2-c*sqrt(n)?

(where c>0 and the balls need not be disjoint?)
This is an embarrassingly simple question, yet somehow I couldn't find an answer (not even, "this is a well-known open problem") after spending some ...

**14**

votes

**1**answer

1k views

### How to keep subsets disjoint?

Given positive integers $n$ and $k\le 2^n$, how to choose a subset $C\subset\{0,1\}^n$ of size $|C|=k$ to maximize the number of pairs $(c_1,c_2)\in C\times C$ with the supports of $c_1$ and $c_2$ ...

**13**

votes

**3**answers

1k views

### A question on representation of graphs

Take a complete graph $K_n$. You want to assign a vectors from $\Bbb F_2^d$ to every edge such that sum of vectors in every simple cycle does not sum to $0$ vector. The question is what is minimum $d$ ...

**13**

votes

**1**answer

624 views

### Maximum number of vectors in a hypercube satisfying given conditions

$\mathcal{C}$ is a collection of binary vectors of length $n$, i.e. $\mathcal{C}\subseteq\{0,1\}^n$. For arbitrary $x,y,z\in\mathcal{C}$ and $x\neq z$, $y\neq z$, there always holds that the Euclidean ...

**11**

votes

**2**answers

498 views

### “The Two Sheriffs” puzzle -2: threshold for security

I've already asked a question “The Two Sheriffs” puzzle with wrong assumption. Yoav Kallus in his amazing answer using Fano plane showed that the problem has a solution in the case of seven suspects.
...

**10**

votes

**3**answers

626 views

### MacWilliams Identity for Asymptotic Weight Spectrum of a Code

Introduction
Let $C$ be a code of block length $n$ having $A_i^C$ words of Hamming weight $i$, for $i\in [n]$, where $[n]:=\{0,\ldots,n\}$. Then, the sequence $\{ A_i^C \}_{i \in [n]} $ is called the ...

**9**

votes

**5**answers

986 views

### covering by spherical caps

Consider the unit sphere $\mathbb{S}^d.$ Pick now some $\alpha$ (I am thinking of $\alpha \ll 1,$ but I don't know how germane this is). The question is: how many spherical caps of angular radius $\...

**9**

votes

**1**answer

298 views

### An isoperimetric problem on the hypercube

Fix integer $n\ge 1$, and let $E=\{e_1,...,e_n\}$ denote the standard basis of the vector space ${\mathbb F}_2^n$. Thus, for a set $A\subset{\mathbb F}_2^n$, the sumset $A+E:=\{a+e\colon a\in A,\ e\in ...

**9**

votes

**0**answers

334 views

### How small parallelograms are we guaranteed to get, when we select the two sides from different plane lattices?

Title question description: Select two lattices $\Lambda_1$ and $\Lambda_2$ (here a lattice=additive free abelian group without accumulation points) of maximal rank two in the real plane. We normalize ...

**8**

votes

**3**answers

1k views

### Hot-topics in error correcting coding related to interesting math. ?

What are topics in error-correcting coding which are related to interesting math. ?
I am primarely interested in nowdays hot topics, but old days topics are also welcome.
Let me try to mention what ...

**7**

votes

**4**answers

1k views

### “sparse graphs are locally tree-like”

I would like to be able to state with confidence that sparse graphs (graphs with small numbers of edges) are locally tree-like (they have few short cycles). Apparently "Sparse graphs are locally tree ...

**7**

votes

**3**answers

661 views

### Error correcting codes - basic question

Hi,
I have a basic question regarding error correcting codes. Suppose I want to encode a finite information $F$ (say a finite string) into a string $x$ of $n$ bits ($n$ can be as large as you want), ...

**7**

votes

**1**answer

2k views

### 12 balls weighing puzzle

In an article describing the twelve balls weighing problem, the author mentions a solution that involves the finite projective plane of order 3, discovered by Rick Wilson. Does anyone know what this ...

**7**

votes

**1**answer

165 views

### lower bound on A(k,4,floor(k/2))

A(k,4,r) is the independence number of the Johnson graph J(k,r).
What is the best known asymptotic lower bound on A(k,4,floor(k/2)) ?
I only obtained $\frac{{k\choose\lfloor{k/2}\rfloor}}{\lfloor{k^2/...

**7**

votes

**2**answers

564 views

### Can you hide a letter without losing information?

Consider the following game between Alice and Bob.
$\Sigma$ is a finite nonempty alphabet, $\Delta \notin \Sigma$ denotes
a special symbol, and $k > 0$ is a positive integer constant representing
...

**7**

votes

**2**answers

549 views

### Automorphisms of subgroup of hamming cube under distance constraint

Let $S$ be a subset of $\{0,1\}^n$ such that any two elements of $S$ are at least (Hamming) distance 5 apart. I'm looking for an upper bound on the size of the automorphism group of $S$.
There's a ...

**6**

votes

**3**answers

358 views

### On the rank of a matrix $S$ with coefficients in $\mathbb F_{2^m}$

Let $\mathbb F$ be a finite field with characteristic 2 and let $S \in M(2k, 2k, \mathbb F)$ be the matrix defined as follows
$$ S=\left[\begin{array}{ccccccc}
0 & \...

**6**

votes

**2**answers

1k views

### Are algebraic geometry error correcting codes (Goppa codes) “good” ?

Question (informal version): Are algebraic geometry error correcting codes (V.D. Goppa codes) "good" ?
Some details. There is certain construction of error-correcting codes by means of algebraic ...

**6**

votes

**2**answers

430 views

### request sources about self-dual cyclic codes

X. Kai and S. Zhu in the paper "On cyclic self-dual codes", AAECC, vol. 19, pp. 509-525, 2008, at page 510 in line 6 said that, It is well Known that there are no cyclic self-dual codes over $F_q$ ...

**6**

votes

**0**answers

96 views

### irregular LDPC code construction algorithm

I want to construct a sparse random binary matrix ${{\bf{H}}_{m \times n}}$ that has the following properties
1- Faction of columns of weight $i$ is ${v_i}$ .
2- Fraction of rows of weight $i$...

**5**

votes

**2**answers

2k views

### Reed-Muller-Codes

Let $F$ be the field with two elements, $V_m=F^{2^m}$.Let $R(r, m)\subset V_m$ be the
binary Reed-Muller Code. Define $R_m:=R(1, m)$. Then the dimension of $R_m$ is
$1+m$ and its minimal distance is ...

**5**

votes

**3**answers

456 views

### Bounded Hamming distance

Definition 1. For each $n\in\mathbb{Z}^+$, the $n$-dimensional Hamming cube is the set of ordered $n$-tuples of $\lbrace 0,1\rbrace$, denoted by $\lbrace 0,1\rbrace ^n$.
Definition 2. The binary ...

**5**

votes

**1**answer

439 views

### Is this graph 3-colorable?

Consider the permutations of $0,1,1,2,2,3,3.$ Each permutation is corresponding to a vertex in graph $G$. So, the graph $G$ has $630$ vertices.
Each vertex has exactly 6 neighbors. $P$ is connected $...

**5**

votes

**1**answer

1k views

### binary code with constant hamming distance

I want as many 80-bits words as possible with the constraint that the hamming distance between any couple of words is exactly 40. How many can I generate? Is there a generic formula telling me how ...

**5**

votes

**2**answers

570 views

### Binary codes with large distance

Suppose $C \subset \lbrace 0,1\rbrace^{n}$ is a binary code with distance $\delta * n$, for $1/2 < \delta < 1$. Can $|C|$ be arbitrarily large (if I allow n to be arbitrarily large)? Note that ...

**5**

votes

**2**answers

431 views

### A Boolean function that is not constant on affine subspaces of large enough dimension

I'm interested in an explicit Boolean function $f \colon \{0,1\}^n \rightarrow \{0,1\}$ with the following property: if $f$ is constant on some affine subspace of $\{0,1\}^n$, then the dimension of ...

**5**

votes

**2**answers

3k views

### If graph is tree what can be said about its adjacency matrix ?

Question If graph is tree what can be said about its adjacency matrix ? And vice versa ?
Especially I am interested in case when graph is bipartite graph.
Such graphs are related to error-...

**5**

votes

**1**answer

159 views

### Finite field analogue of Chebotaryov theorem on roots of unity?

Chebotarev's theorem on roots of unity says that all the minors of a prime-length DFT matrix over the complex numbers are nonzero. I was wondering if there was an analogue for finite fields.
More ...

**5**

votes

**0**answers

218 views

### When does the Lloyd polynomial have only integral roots?

For a $t$-error correcting code of length $n$ over the finite field $\mathbb{F}_q$, the Lloyd polynomial is given by
$$
L_t(n,x):=\sum_{j=0}^t(-1)^j\binom{x-1}{j}\binom{n-x}{t-j}(q-1)^{t-j}.
$$
A well-...

**4**

votes

**3**answers

476 views

### Good codes in practice for correcting combination of errors and erasures

In practice, both errors and erasures might be introduced in the channel. Could you point me to some good codes for correcting such combinations. Also what are their correction capabilities?

**4**

votes

**2**answers

255 views

### Is there a code which corrects corruption of any two bits in a block?

Background
I've just learned a bit about linear codes. Hamming codes have the property that up to one bit in a block can be corrupted, and we still communicate the message correctly. This is done by ...

**4**

votes

**1**answer

167 views

### Lower bound on the dimension of a subspace of $\mathbb Z_2^r$?

This question may be very trivial, I apologize if it is so.
I have subspace $V\subset \mathbb Z_2^r$ with the property that for every choice of a subset $I$ of $k$ elements in $\{1,2,\dots r\}$, the ...

**4**

votes

**1**answer

336 views

### Best upper bound on rate for q-ary codes

Among the many upper bounds for families of codes in $\mathbb F _2 ^n$, the best known bound is the one by McEliece, Rodemich, Rumsey and Welch which states that the rate $R(\delta)$ corresponding to ...

**4**

votes

**2**answers

277 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}...

**4**

votes

**4**answers

631 views

### how to find vector $(\pm 1, \pm 1, \pm 1, … \pm 1)$ which is most close to given vector (r_1,…r_l) ? Is it NP-problem ? What algorithms are available ?

Given:
some vector $R=(r_1...r_l)$ - real numbers,
and a set of distinct vectors with $+1$ or $-1$ coordinates
$$\begin{array}{c} V_1=(c_{1,1} ... c_{1,l}),\\\
V_2=(c_{2,1} ... c_{2,l}),\\\
.....

**4**

votes

**1**answer

227 views

### Is the direct sum in Maschke's Theorem an orthogonal decomposition?

I am reading a paper on coding theory, and it uses a statement, which was claimed to be a reformulation of Maschke's Theorem. But I felt that was false...
Let's say $\mathcal(V):=\mathcal{F}_2^n$ is ...

**4**

votes

**2**answers

162 views

### Another formulation of error-correcting coding problem

Consider classic error-correcting problem:
there is finite set $A$ and string $a_1...a_n$, $a_i \in A$ in the begin.
in the end we have $b_1...b_n$. Set places of errors $E = \{i| a_i\not= b_i \}$, ...

**4**

votes

**1**answer

392 views

### Probability of false decoding with LDPC codes

It is well known that given a binary linear code $C$ under maximum likelihood decoding the probability of false decoding $P_C$ in a Binary Symmetric Channel with cross over probability $p$, in other ...

**4**

votes

**1**answer

132 views

### Balanced binary code that “resists” local decoding?

I am looking for a construction that can be stated as the following coding problem: a binary code with good distance ($d = \Omega(n)$ where codeword length is $n$) that "resists local decoding" in the ...

**4**

votes

**1**answer

198 views

### Partial backups

Suppose you have some storage medium of a given size M, and can make some kind of backup on another medium of size B with M > B. You can choose the scheme to determine the contents of the backup.
...

**4**

votes

**1**answer

252 views

### Most orthogonal lattice basis

Let $n \in \mathbf{N}$ be a natural number and $v_1,\cdots,v_n$ a set of basis vectors in $\mathbb{R}^n$. How does one find the matrix $g \in \mathbf{GL}_n(\mathbb{Z})$ orthogonalizing these best ...

**4**

votes

**1**answer

488 views

### Intersecting Hamming spheres: is $|A\stackrel k+E|\ge|A|$?

Since my original posting some ten days ago, I discovered an amazing
example which changed significantly my perception of the problem.
Accordingly, the whole post got re-written now.
The most ...

**4**

votes

**0**answers

127 views

### Application of finding shortest paths on Cayley graphs

For a fixed integer number $m$, Consider Cayley graph defined by all m-cycles in Symmetric group $Sym(n)$.
I know that for $m=2$,
there are some applications of finding shortest paths (or distance ...

**4**

votes

**0**answers

157 views

### Fully Homomorphic Error Correction?

Consider a field $F$. Suppose we have two vectors $a,b\in F^n$, and an invertible matrix $G\in F^{n\times n}$. Let $c\in F^n$ be the point-wise product of $a$ and $b$, that is, $c_i=a_ib_i$. Let $x=...

**3**

votes

**3**answers

592 views

### Structure of F_p[G], for finite group G ?

Consider group algebra k[G] of finite group G.
If k is alg.closed then every irrep lives there with multiplicity equal to dimension.
(More conceptually as bimodule over GxG it is multiplicity free and ...

**3**

votes

**3**answers

3k views

### Computing channel capacities for non-symmetric channels

I'm studying information theory right now and I'm reading about channel capacities.
I know that there are known expressions for computing the capacities for some well known simple channels such as ...