Hypergraph stability after subtraction

The presented methods for assessing stability are applicable only to a hypergraph with a specific basis through the mechanism of redefining the original vectors.

Cryptographic structures on hypergraphs cannot be adequately represented by ordinary graphs. To work with these bases, we will define the key characteristics and methods that we will rely on in this and subsequent publications.

Methods from combinatorics, probability estimation (higher moments of distribution), dispersion analysis in stability assessment, and logarithmic normalization to avoid excessively large numbers are involved.

The methods described in this document are applicable only to structure assessment after subtraction, for all other operations, a specific evaluation basis is described.

To start it is necessary to consider the sum under the logarithm:

{i1,i2,i3,i4}=4,{j1,j2,j3,j4}=4(1r2+ϵi1j1)(1r2+ϵi2j2)(1r2+ϵi3j3)(1r2+ϵi4j4)\sum_{\{i_1, i_2, i_3, i_4\}=4, \{j_1, j_2, j_3, j_4\}=4} \left(\frac{1}{r^2} + \epsilon_{i_1 j_1}\right) \left(\frac{1}{r^2} + \epsilon_{i_2 j_2}\right) \left(\frac{1}{r^2} + \epsilon_{i_3 j_3}\right) \left(\frac{1}{r^2} + \epsilon_{i_4 j_4}\right)

Simplify the sum:

=r2(r1)2(r2)2(r3)2r8+4i1,j1=1rϵi1j1(r1)2(r2)2(r3)2r6 += \frac {r^2 (r-1)^2 (r-2)^2 (r-3)^2}{r^8} + 4 \sum_{i_1, j_1=1}^{r} \epsilon_{i_1 j_1} \frac{(r-1)^2 (r-2)^2 (r-3)^2}{r^6}\ +
+ 6{i1,i2}=2,{j1,j2}=2ϵi1j1ϵi2j2(r2)2(r3)2r4+4{i1,i2,i3}=3,{j1,j2,j3}=3ϵi1j1ϵi2j2ϵi3j3(r3)2r2 ++\ 6 \sum_{\{i_1, i_2\}=2, \{j_1, j_2\}=2} \epsilon_{i_1 j_1} \epsilon_{i_2 j_2} \frac{(r-2)^2 (r-3)^2}{r^4} + 4 \sum_{\{i_1, i_2, i_3\}=3, \{j_1, j_2, j_3\}=3} \epsilon_{i_1 j_1} \epsilon_{i_2 j_2} \epsilon_{i_3 j_3} \frac{(r-3)^2}{r^2}\ +
+{i1,i2,i3,i4}=4,{j1,j2,j3,j4}=4ϵi1j1ϵi2j2ϵi3j3ϵi4j4+ \sum_{\{i_1, i_2, i_3, i_4\}=4, \{j_1, j_2, j_3, j_4\}=4} \epsilon_{i_1 j_1} \epsilon_{i_2 j_2} \epsilon_{i_3 j_3} \epsilon_{i_4 j_4}

Using the results of the proof:

i,j=1rϵij=0;{i1,i2}=2,{j1,j2}=2ϵi1j1ϵi2j2=i,j=1rϵij2;{i1,i2,i3}=3,{j1,j2,j3}=3ϵi1j1ϵi2j2ϵi3j3=4i,j=1rϵij3;\sum_{i,j=1}^{r} \epsilon_{ij} = 0; \quad \sum_{\{i_1, i_2\}=2, \{j_1, j_2\}=2} \epsilon_{i_1 j_1} \epsilon_{i_2 j_2} = \sum_{i,j=1}^{r} \epsilon_{ij}^2; \quad \sum_{\{i_1, i_2, i_3\}=3, \{j_1, j_2, j_3\}=3} \epsilon_{i_1 j_1} \epsilon_{i_2 j_2} \epsilon_{i_3 j_3} = 4 \sum_{i,j=1}^{r} \epsilon_{ij}^3;
{i1,i2,i3,i4}=4,{j1,j2,j3,j4}=4ϵi1j1ϵi2j2ϵi3j3ϵi4j4=3(i,j=1rϵij2)218i,j=1rϵij2ϵi1j12\sum_{\{i_1, i_2, i_3, i_4\}=4, \{j_1, j_2, j_3, j_4\}=4} \epsilon_{i_1 j_1} \epsilon_{i_2 j_2} \epsilon_{i_3 j_3} \epsilon_{i_4 j_4} = 3 \left( \sum_{i,j=1}^{r} \epsilon_{ij}^2 \right)^2 - 18 \sum_{i,j=1}^{r} \epsilon_{ij}^2 \epsilon_{i_1 j_1}^2

Based on these results we will obtain confirmation of the correctness of formula γ(Υ)\gamma(\Upsilon).

Essential components need to be identified.

Quadratic distribution effects:

1+6(rr1)2i,j=1rϵij21 + 6 \left( \frac{r}{r-1} \right)^2 \sum_{i,j=1}^{r} \epsilon_{ij}^2

Determination of cubic effects that can significantly affect distribution (it is important to maintain the principle of normal distribution for all elements including noise components):

16r4(r1)2(r2)2i,j=1rϵij316 \frac{r^4}{(r-1)^2 (r-2)^2} \sum_{i,j=1}^{r} \epsilon_{ij}^3

Interaction between sub edges through quadratic sums:

3r6((r1)(r2)(r3))2(i,j=1rϵij2)23 \frac{r^6}{((r-1)(r-2)(r-3))^2} \left( \sum_{i,j=1}^{r} \epsilon_{ij}^2 \right)^2

Final definition:

γ(Υ)=cln(1+6(rr1)2i,j=1rϵij2+16r4(r1)2(r2)2i,j=1rϵij3 +\gamma(\Upsilon) = c \ln \left( 1 + 6 \left( \frac{r}{r-1} \right)^2 \sum_{i,j=1}^{r} \epsilon_{ij}^2 + 16 \frac{r^4}{(r-1)^2 (r-2)^2} \sum_{i,j=1}^{r} \epsilon_{ij}^3\ +\right.
+ 3r6((r1)(r2)(r3))2(i,j=1rϵij2)218r6((r1)(r2)(р3))2i,j1,j3=1rϵij12ϵij32 ++\ 3 \frac{r^6}{((r-1)(r-2)(r-3))^2} \left( \sum_{i,j=1}^{r} \epsilon_{ij}^2 \right)^2 - 18 \frac{r^6}{((r-1)(r-2)(р-3))^2} \sum_{i, j_1,j_3=1}^{r} \epsilon_{ij_1}^2 \epsilon_{ij_3}^2\ +
+36r6((r1)(р2)(р3))2i,j=1рϵij4+6r6((р1)(р2)(р3))2i1,j3,j1,j3=1рϵi1j1ϵi1j3ϵi1j3ϵi1j3)+ 36 \frac{r^6}{((r-1)(р-2)(р-3))^2} \sum_{i,j=1}^{р} \epsilon_{ij}^4 + 6 \frac{r^6}{((р-1)(р-2)(р-3))^2} \sum_{i_1,j_3,j_1,j_3=1}^{р} \epsilon_{i_1 j_1} \epsilon_{i_1 j_3} \epsilon_{i_1 j_3} \epsilon_{i_1 j_3})

Implementation for clarity (without optimization):

let sum_log hg n r =
  let eps = Lst.mapi (fun _ row -> Lst.mapi (fun _ a -> eps a n r) row) hg in
  let sum_eps k =
    let flat_eps = List.flatten eps in
    List.fold_left (fun acc e -> acc +. (e ** float_of_int k)) 0.0 flat_eps
  let sum_cross () =
    List.fold_left (fun acc row -> acc +. List.fold_left (fun acc' e -> acc' 
    +. (e ** 2.0)) 0.0 row) 0.0 eps
  let r_f = float_of_int r in
  let cf = (r_f ** 6.0) /. ((r_f -. 1.0) ** 2.0 *. (r_f -. 2.0) *. (r_f -. 3.0)) ** 2.0 in
  1.0 +.
  6.0 *. ((r_f /. (r_f -. 1.0)) ** 2.0) *. sum_eps 2 +.
  16.0 *. ((r_f ** 4.0) /. ((r_f -. 1.0) ** 2.0 *. (r_f -. 2.0) ** 2.0)) *. sum_eps 3 +.
  3.0 *. cf *. (sum_eps 2 ** 2.0) -.
  18.0 *. cf *. sum_cross () +.
  36.0 *. cf *. sum_eps 4 +.
  6.0 *. cf *. sum_cross ()

Preserving the structure of a hypergraph after a series of subtraction operations does not lead to a change in the structure, the immutability of the hypergraph allows us to clearly understand that even after a series of large changes and noise, this does not lead to the loss of the ability to perform subtractions, as was proven earlier.

Last updated