# Tagged Questions

**3**

votes

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**3**answers

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

**2**answers

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

**1**answer

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

**2**answers

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

**2**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**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 ...

**4**

votes

**2**answers

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

**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 ...