расстояние хемминга, подсчет числа последовательностей

[ewert]

Kallikanzarid в сообщении #466676 писал(а):

руководствуйтесь тем, что $\rho(x,y) = \rho(x - y, 0) =: \|x - y\|$ - это норма на векторном пространстве $\mathbb{Z}_2^n$,

Это не норма. Над каким полем то пространство?...

[4aineg]

LaTeXScience
не совсем понял почему они должны равняться 2м, у нас же тут либо 0 либо 1?
1)а если бы с теми же векторами т.е. их $\rho(\alpha,\beta)=3$
$\rho(\alpha,\gamma)+\rho(\gamma,\beta)=5$
то тут были бы решения?
просто мне кажется что тут от четности может зависеть

2)а если такой пример

$\alpha = (111100)$,
$\beta = (000000)$

и необходимо чтобы выполнилось
$\rho(\alpha,\gamma)+\rho(\gamma,\beta)=3$
тут так же не будет решений?

-- Вт июл 12, 2011 14:31:21 --

ewert

над полем $GF(2)$

[ewert]

Увы. Значения "нормы" не втискиваются в это поле -- и, значит, это не норма.

[LaTeXScience]

4aineg в сообщении #467562 писал(а):

1)а если бы с теми же векторами т.е. их $\rho(\alpha,\beta)=3$
$\rho(\alpha,\gamma)+\rho(\gamma,\beta)=5$
то тут были бы решения?

Да. Например, $\alpha=(0101101)$, $\beta=(1000101)$, $\gamma=(0000111)$.

4aineg в сообщении #467562 писал(а):

просто мне кажется что тут от четности может зависеть

Можно доказать, что если $\rho(\alpha,\beta)=k$, то сумма $\rho(\alpha,\gamma)+\rho(\alpha,\gamma)$ может принимать значения только вида $k+2m$.

4aineg в сообщении #467562 писал(а):

2)а если такой пример

$\alpha = (111100)$,
$\beta = (000000)$

и необходимо чтобы выполнилось
$\rho(\alpha,\gamma)+\rho(\gamma,\beta)=3$
тут так же не будет решений?

Не будет, это следует уже из неравенства треугольника.

4aineg в сообщении #467562 писал(а):

не совсем понял почему они должны равняться 2м, у нас же тут либо 0 либо 1?

Потому что, например, $A_3=\rho_1(0,\gamma_3)+\rho_1(0,\gamma_3)=2\rho_1(0,\gamma_3)$. Ноль либо один это $\rho_1(\alpha_i,\beta_i)$, а $A_i$ могут принимать значения 0, 1 и 2.

[Kallikanzarid]

ewert в сообщении #467486 писал(а):

Это не норма. Над каким полем то пространство?...

Над полем $\mathbb{Z}_2$. Почему это не норма? Вводим "модуль" на $\mathbb{Z}_2$ как $|1| = 1,\ |0| = 0$ (не норма поля, но разве это страшно?). Проверяем: $0 = |1 + 1| \leq |1| + |1| = 2$ - выполняется, $|1 \cdot 1| = |1| \cdot |1|$, $|0 \cdot 1| = |0| \cdot |1|$ - и т. д. Затем вводим норму $\|\cdot\|: \mathbb{Z}_2^n \to \mathbb{N} \to \mathbb{R}_{\geq 0}$. Странно слышать такие претензии: метрику же мы как-то ввели, а норма - всего лишь способ работать с хорошими метриками на векторных пространствах. Соответствующая топология получается дискретной - вполне естественно.

[ewert]

Kallikanzarid в сообщении #467606 писал(а):

метрику же мы как-то ввели,

Да, ввели. Но не норму. Поскольку понятие нормы осмысленно лишь для линейных пространств. Изначально наше пространство не было снабжено линейной структурой, поэтому метрику мы имели полное право вводить как заблагорассудится. Но как только линейная структура введена -- любая норма имеет право принимать значения лишь из соответствующего поля. Поскольку иначе теряет формальный смысл аксиома однородности.

[LaTeXScience]

LaTeXScience в сообщении #467577 писал(а):

сумма $\rho(\alpha,\gamma)+\rho(\alpha,\gamma)$

Т.е. я хотел сказать $\rho(\alpha,\gamma)+\rho(\beta,\gamma)$.

[Kallikanzarid]

ewert в сообщении #467620 писал(а):

Но как только линейная структура введена -- любая норма имеет право принимать значения лишь из соответствующего поля.

Можно ссылку на источник? И, главное, если мы определим норму Хэмминга тем образом, который я продемонстрировал, какие у нее возникнут нехорошие свойства?

[ewert]

Kallikanzarid в сообщении #467704 писал(а):

Можно ссылку на источник?

Можете дать определение нормы?

[Kallikanzarid]

ewert в сообщении #467712 писал(а):

Можете дать определение нормы?

Ну, например: пусть $K$ - поле с заданным на нем абсолютным значением $|\cdot|: K \to \mathbb{R}$, удовлетворяющим условиям положительной определенности, невырожденности, неравенству треугольника и $|ab| = |a||b|$, а $V$ - векторное пространство над $K$. Тогда нормой называется отображение $\|\cdot\|: V \to \mathbb{R}$, удовлетворяющее условиям бла-бла-бла...

Я понимаю, что вы хотите рассматривать норму на поле (а ее кодомен - поле, расширением которого является домен). Но геометрически норма векторного пространства возникает из рассмотрения равномерных метрик, инвариантных относительно сдвигов (т.е. в точности таких, метрические топологии которых превращают $V$ в топологическое векторное пространство). Здесь приходится обобщать абсолютное значение на $\mathbb{R}$ и $\mathbb{C}$ по-другому.

Это мои собственные мысли, во всех источниках, которые я видел, нормированные векторные пространства рассматривают только над $\mathbb{R}$ и $\mathbb{C}$. Но я слышал, как "норму" Хэмминга называли нормой довольно серьезные люди, и я не вижу в этом серьезной проблемы, учитывая то, для чего используется норма. Если у вас есть возражения (еще лучше - подкрепленные ссылками на работы, посвященные нормированным векторным пространствам над другими полями), я готов их рассмотреть.

[4aineg]

мне кажется в пространстве $B^7$ это уж слишком сильно))

[Sonic86]

4aineg в сообщении #467413 писал(а):

конечная формула:
$2^{\rho(\alpha,\beta)} {n \choose k} = 32$

А у меня получилось, что $\rho = \rho(\alpha,\beta) + 2m$ и тогда число решений $N=2^{\rho(\alpha,\beta)} \binom{n - \rho(\alpha,\beta)}{m}$ ($n$-размерность пространства).

[4aineg]

Цитата:

А у меня получилось, что $\rho = \rho(\alpha,\beta) + 2m$ и тогда число решений $N=2^{\rho(\alpha,\beta)} \binom{n - \rho(\alpha,\beta)}{m}$ ($n$-размерность пространства).

действительно так) а в нашем сучае т.к. $\rho(\alpha,\gamma) + \rho(\gamma, \beta) - \rho(\alpha,\beta) = 1$ нечетно, поэтому нет решений

а в случае с примером:
$\alpha = (1111000) \beta = (0000000)$

$\rho(\alpha,\gamma) + \rho(\gamma, \beta) \ge 3$
тогда у нас получится:
$2^{4}(\binom{3}{1}+\binom{3}{2}+\binom{3}{3})$
ведь так? или нет

[Sonic86]

4aineg в сообщении #469550 писал(а):

ведь так? или нет

да, получается так.

[pashabond]

Не могли бы объяснить параметр m в итоговой формуле $N=2^{\rho(\alpha,\beta)} \binom{n - \rho(\alpha,\beta)}{m}$, если можно на примере второй задачи, m = 1 вроде как, как получилось?