НИЖНЯЯ И ВЕРХНЯЯ ОЦЕНКИ ПОРЯДКА АФФИННОСТИ ПРЕОБРАЗОВАНИЙ ПРОСТРАНСТВ БУЛЕВЫХ ВЕКТОРОВ

  • View
    214

  • Download
    2

Embed Size (px)

Transcript

  • 2013

    2(20)

    510.52

    .. , . .

    , , . , , . ,

    E-mail: spg54@bk.ru

    - n- . .

    : , , .

    :N ;Vn n- , n N;n Vn Vn;0n = (0, . . . , 0

    n

    )T ;

    bcc c, g(n), h(n) n N

    n0 N, n > n0 g(n) < h(n),

    g(n)

  • 15

    {f1, . . . , fn} F . (1) -

    F (x) = , (2)

    x = (x1, . . . , xn), =

    1. . .n

    . A1, . . . , AardF , F . (1)

    ( (2)) -:

    Ai(x) = , i = 1, . . . , ardF,

    (2). , ardF .

    .

    ardn = maxFn

    ardF.

    ardn n. ardn (2).

    1. n > 2

    ardn >2n

    n2.

    . , Vn Vn 2n(n+1).

    A1, . . . , A2n(n+1) (3)

    n. u ardn. F n Vn M1, . . . ,Mk,k 6 u, Ai1 , . . . , Aik , , Aij F Mj,j {1, . . . , k}. , Ml , , Ai1 , . . . , Aik u .

    h n, - u :

    h 6

    (2n(n+1)

    u

    ) u2n . (4)

    (4) , Ai1 , . . . , Aiu (3). Ai1 , . . . , Aiu , u2n F n, F (), Vn, u .

    , h < 2un(n+1) u2n . (5)

    (5) 2,

    log2 h < un(n+ 1) + 2n log2 u. (6)

  • 16 .. , . .

    ,

    ardn 62n

    n2.

    (6) ,

    log2 h < 2n

    (n+

    n(n+ 1)

    n2 2 log2 n

    ). (7)

    n > 2 (7)

    log2 h < n 2n. (8)

    u n, h = |n| = 2n2n ,

    log2 h = n 2n. (9)

    (8) (9) , ardn >2n

    n2.

    ardn. - .

    , . 1. {((1), (1)), . . . , ((m), (m))} Vn,

    m 6 n, {(1), . . . , (m)} . - L n, ,

    L((i)) = (i), i = 1, . . . ,m.

    2. M Vn, |M | > 2k, k {0, . . . , n 1}, M. M k + 1 .

    . , (, ) t < k+ 1 . (1), . . . , (t). M - (1), . . . , (t), M = M \ {0n}. , M M , |M | > 2k. , |M | = 2t1 6 2k1 < 2k. .

    2. n > 2 :

    ardn 62n

    n

    n1i=1

    2i nn i

    .

    . F , n. F : Vn ( r). ( {(1)1 , . . . ,

    (1)n }) F

    , F (0n). 1,

    L n, L((1)i ) = F ((1)i ) F (0n), i = 1, . . . , n.

  • 17

    L(x) F (0n) F {(1)1 , . . . ,

    (1)n , 0n}.

    r1 , 1, F - . , ardn 6 r.

    r. Vn \{0n}, n > 1,

    Vn \ {0n} = 2n 1 > 2n1. 2, Vn \ {0n} n (1)1 , . . . ,

    (1)n .

    M = Vn \ {(1)1 , . . . , (1)n , 0n} |M | > 2n1,

    n (2)1 , . . . , (2)n , ,

    M = Vn \ ({(1)1 , . . . , (1)n , 0n} {

    (2)1 , . . . ,

    (2)n } . . . {(rn1)1 , . . . ,

    (rn1)n })

    |M | < 2n1. rn1 n , rn1 ,

    rn1 =2n 1 (2n1 qn1)

    n=

    2n1 1 + qn1n

    ,

    qn1 = n, (2n1 1)/n; qn1 {1, . . . , n 1} , (2n1 1 ++qn1)/n , (2n1 1)/n.

    n 1 .

    rn2 =2n1 qn1 (2n2 qn2)

    n 1=

    2n2 qn1 + qn2n 1

    ,

    qn2 {1, . . . , n 1}, . ,

    ri =2i+1 qi+1 (2i qi)

    i+ 1=

    2i qi+1 + qii+ 1

    i+ 1 , qi {1, . . . , i+ 1}, i 0, . . . , n 2.

    r = rn1 + rn2 + . . .+ r0 =2n1 1 + qn1

    n+

    2n2 qn1 + qn2n 1

    + rn3 + . . .+ r0 =

    =1

    n 1

    (n 1n

    (2n1 1 + qn1) + 2n2 qn1 + qn2)

    + rn3 + . . .+ r0 =

    =1

    n 1

    (2n1 2

    n1

    n+ 2n2 + qn2

    (qn1n

    +n 1n

    ))+ rn3 + . . .+ r0 6

    62n1

    n 1+

    2n2 1 + qn2n 1

    + rn3 + rn4 + . . .+ r0 =

    =2n1

    n 1+

    (2n2 1 + qn2

    n 1+

    2n3 qn2 + qn3n 2

    )+ rn4 + . . .+ r0 6

    62n1

    n 1+

    2n2

    n 2+

    (2n3 1 + qn3

    n 2+

    2n4 qn3 + qn4n 3

    )+ rn5 + . . .+ r0 6

    62n1

    n 1+

    2n2

    n 2+ . . .+

    22

    2+

    (21 1 + q1

    2+

    20 q1 + q01

    )=

    =2n1

    n 1+

    2n2

    n 2+ . . .+

    22

    2+

    21

    1=

    2n

    n

    (21

    n

    n 1+ 22

    n

    n 2+ . . .+ 2(n1)

    n

    1

    ).

    .

  • 18 .. , . .

    3.

    limn

    n1i=1

    2in

    n i= 1.

    . :

    n1i=1

    2in

    n i=b3 log2 nci=1

    2in

    n i+

    n1i=b3 log2 nc+1

    2in

    n i. (10)

    (10) S1, S2. ,

    b3 log2 nci=1

    2i < S1