3
votes
1answer
448 views

“Codes” in which a group of words are pairwise different at a certain position

I read the following problem, claimed to be in the IMO shortlist in 1988: A test consists of four multiple choice problems, each with three options, and the students should give an unique answer ...
1
vote
1answer
291 views

Cyclic Hamming Code

I know that Hamming codes can be arranged in cyclic form. But my question is how can I prove this. My idea was to find a generator/primitive polynomial $p(x)$? For example I want to show that the ...
3
votes
1answer
122 views

Reference for partial Hadamard matrices

Definition. An $m\times n$ matrix is said to be a partial Hadamard matrix (let's say PHM) if its entries are chosen from $\lbrace -1, 1 \rbrace$ such that the dot product of each pair of row vectors ...
5
votes
0answers
160 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 ...
1
vote
1answer
146 views

Extended Hypercube Graph

Definition 1. The $n$-hypercube graph has vertices which are the elements of the set $\lbrace 0,1\rbrace^n$ of $n$-bit binary strings, and an edge is drawn between each pair of vertices representing a ...
4
votes
3answers
285 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 ...
1
vote
2answers
361 views

Hamming codes from overlapping vectors

I am interested in whether the following problem is known. For a given binary vector $V$ of length $n\geq m$, let $S$ be a subset of the possible subvectors of $V$ of length $m$ and say that the size ...
4
votes
1answer
194 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 ...
7
votes
2answers
524 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 ...
3
votes
2answers
265 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}, ...
0
votes
1answer
119 views

How many combinations exist of $M'$ items from a set of $M$ items such that each combination is not similar at more than $m$ elements?

I apologize if this has been answered before. I would like to know how many ways there are to choose $M'$ elements from a set of $M$ elements such that any two sets selected are not similar at more ...
3
votes
1answer
257 views

The chromatic number of a Hamming-related graph

For integer $1\le k\le n$, let ${\overline H}_n^k$ denote the complement of the $k$-th power of the Hamming graph on the vertex set ${\mathbb F}_2^n$; that is, two vectors from ${\mathbb F}_2^n$ are ...
1
vote
1answer
355 views

A covering problem for the Hamming cube

Consider the set of all $k$-subsets of $\{1,\dots,n\}$, naturally identified with a subset $A$ of $\{0,1\}^n$ where each element has exactly $k$ ones. Is there a sharp bound known for ...
1
vote
1answer
153 views

What are the key applications of the MacWilliams identities in coding theory?

The MacWilliams identities relate the weight enumerators of a code and its dual code. I treated the version for linear codes in my combinatorics class, but felt unsatisfied because I didn't have a use ...
4
votes
1answer
406 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 ...
9
votes
1answer
274 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 ...
0
votes
0answers
105 views

A search for optimal order ideals

At the behest of Gerhard Paseman I'll describe the problem that I alluded to in name for a partial order. Let $M = M(\infty)$ denote the set of all finite subsets of the positive integers ...
4
votes
1answer
254 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 ...
0
votes
1answer
318 views

Fixed Hamming distance property of binary deletion correcting codes

Let $x=(x_1x_2...x_n)$ be a binary sequence of length $n$. The Varshamov-Tenengolts code $VT_0(n)$ consists of all binary vectors $(x_1, . . . , x_n)$ satisfying $\Sigma_{i=1}^n i*x_i \equiv0 \pmod ...
14
votes
1answer
864 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$ ...
1
vote
1answer
276 views

Large subgroups of the Hamming cube

Let's consider the abelian group $\mathbb{Z}^N_2$ equipped with the Hamming metric (the hypercube). Suppose I have a subgroup of this hypercube (not necessarily a subcube) which is generated by a set ...
7
votes
4answers
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 ...
4
votes
2answers
356 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 ...
7
votes
1answer
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 ...