Btukfyl

Suppose I want to communicate an integer to a friend between 1 and 1000. In order to pass this message I use a $k$-vector whose entries can be set to $0$ or $1$. So for example if $k=3$, a natural way to express the number $7$ is $langle 1,1,0rangle$, where this corresponds to the binary representation $2^2+2^1+2^0$ for $7$.

However, there is a wrinkle! Before my friend can view my vector, he must pass it through a function $f_i$ which is the identity on all components not equal to $i$, and which sets the $i$-th component to $1$. For example, $f_1(langle 1,1,0rangle) = langle 1,1,0rangle$, but $f_3(langle 1,1,0rangle) = langle 1,1,1rangle$.

Critically, the value of $i$ is unknown to both me and my friend. The challenge is:

What is the smallest $k$ such that my friend can always understand my
number?

My thought process:

Clearly if there were no error $k=10$ would be sufficient. If I simply wanted my friend to know if the message were changed $k=11$ would be sufficient, since I would agree to represent all numbers using a $1$-even representation (i.e. a $k$-binary with an even number of $1$s) and if my friend received an odd number he would know one of the $1$s would have been changed.

Of course he must be able to recover a garbled message. Therefore, all $1$-even vectors which could have plausibly "degenerated" into a $1$-odd vector must be considered equivalent. Therefore I think one can reduce the problem to smaller problems. Let $A^k_j$ be the set of all $k$-vectors with exactly $j$ ones. For all even $j<k$, what is the largest subset $S_j^ksubset A_j^k$ such that no two elements of $S_j^k$ can degenerate into the same vector in $A_{j+1}^k$. If we solve this, then we can sum these maximal cardinalities over all even $j$ and obtain the result.

However, it's not clear how to finish! I'm aware that this seems vaguely related to error correcting codes and Hamming distance - I think the reduced problem can plausibly be reduced to a question about subsets of the permutation group. But I can't quite figure it out...

Edit: Clearly you can let $k=22$ and just repeat your message twice, constraining the message to be 1-even. This is a crude upper bound. I am quite sure one can do much better than this...

Update: Can currently get to as low as k=15

I can do $k=15$ as follows: Let $mathbf{v}$ be your original $k$-vector. First encode the message as a $1$-even message with the first $11$ digits. If the message is uncorrupted, your friend will know and you will be done. If it is corrupted, the remaining $4$ digits tell your friend the value of $sum_{i=1}^{11} v_i cdot i (text{mod} 10),$ from which you can infer which digit was flipped.

Let me use, as usual, $k$ for the "data bits" and $n$ for the total bits sent, with $n-k$ being the redundancy.

$n=14$ bits should be enough

Take $k=10$ , $n-k=4$. Build a Hamming parity check with $n-k=4$ rows, placing the $2^4$ distinct columns, except for the null column and some extra column (I chose the all-ones column) :

$$H=begin{pmatrix}
1&0&0&0&1&1&1&0&0&0&1&1&1&0\
0&1&0&0&1&0&0&1&1&0&1&1&0&1\
0&0&1&0&0&1&0&1&0&1&1&0&1&1\
0&0&0&1&0&0&1&0&1&1&0&1&1&1
end{pmatrix}=( I_4 mid P)
$$

The corresponding generator matrix is

$$ G= (P^t , | , I_{10})$$

This linear code (a shortened Hamming code) has distance $d=3$ (because you need at least three columns to get a LD set), so you can correct a single error. (Not only $0to 1$ but also $1 to 0$)

And you can trasmit $2^k=1024$ values (more than $1000$).

Because this encoding corrects more errors than needed (we have some kind of Z-channel, instead of a BSC channel), it remains to be seen if $n$ can be further reduced.

This may not be the best possible, but I think it works.

[Added: After I posted my answer, I saw that the OP found a similar, but better, strategy to send the message using one fewer bit.]

Encode the number $N$ as a $10$-bit base-$2$ value $b_1b_2dots b_{10}$, and then send an $16$-bit message comprising your number followed by the binary representation of $f(N)=b_1+2b_2+3b_3+4b_4+5b_5+6b_6+7b_7+8b_8+9b_9+10b_{10}$
(which is between $0$ and $55$, so requires $6$ bits). Share the formula for $f$ with your friend.

Your friend decodes the first $10$ bits of the message as $x$ and the last $6$ bits as $F$. If $F=f(x)$, then your message was $x$. If $F<f(x)$, then a $0$ bit of $x$ was set to $1$ during transmission. The value of $f(x)-F$ tells you which bit it was, and $N=x-2^{10-f(x)+F}$. If $F>f(x)$, a $0$ bit of $f(N)$ was set during transmission, and $N=x$.

[Ok, I am amending my waaay suboptimal answer (which I gave after misreading the question and used k=30 in a trivial way).]

This is my new solution with k=14 (which in my comments showed cannot be improved) [I see leonbloy already posted a solution with k=14 using Hamming code, mine goes more in the direction previously tried by the OP].

Let ${v_i}_{i=1}^{10}$ the 10 components (0's and 1's) of your binary vector. Let $x$ be
$$
x = 3v_1 + 5v_2 + 6v_3 + 7v_4 + 9v_5 + 10v_6 + 11v_7 + 12v_8 + 13v_9 + 14v_{10}
$$
(note I have omitted coefficients that are exact powers of 2).
Then compute $y = x pmod{16}$, express it as a binary number with 4 bits, and append it to your string. You get a 14-bit binary string, and send it to your friend. Your friend computes $x pmod{16}$ and compares it to $y$ from the string he receives. If the difference is not a power of 2 then it tells him which coefficient is missing in the formula used to compute his $x$, and which bit has been altered in your original vector. If it is a power of 2, then the part altered is $y$, and your original vector has not been modified.

Would that work?