Regular fractions in literature

Comparison of different definitions of regular fraction

Maria Piera Rogantin

DIMA – Universit`a di Genova – [email protected]

Giovanni Pistone

DIMAT – Politecnico di Torino – [email protected] SCRA 2006, Tomar - Portugal, September 1-4, 2006

Regular fractions in literature

• Generating words:

– If the level number is a prime number, n = p: generating words in

“additive” notation and computation in Z_p (integer coding)

– If the level number is a power of a prime number, n = p^s: gener- ating words and computation in GF(p^s) [e.g.: Dey and Mukerjee (1999)]

– Complex coding: generating words in “multiplicative” notation and computation in C [Bailey (1982), . . . , Kobilinsky (1997), . . . , Pistone and Rogantin (2005)]

• Property of non-existence of partial aliasing (associated to a spe- cific basis of responses) [e.g.: Wu and Hamada (2000)]

Assumption:

symmetrical fractional factorial designs (same number of levels n)

Regular fractions in complex coding

Pistone, G., Rogantin, M.-P., 2005. Indicator function and complex cod- ing for mixed fractional factorial designs. Submitted to JSPI.

Complex coding for levels

We code the n levels of a factor A with the n-th roots of the unity:

ω_k = exp



i 2π n k



for k = 0, . . . , n − 1 Ω_n = {ω₀, . . . , ω_n−1}

w

w w1

0

2

Regular fraction

^:

two factors or interactions are either orthogonal or totally aliased

Outline

• All definitions are equivalent if all factors have the same prime num- ber of levels n = p

• Case n = p^s:

G

F

S ( _Ω

_p^s

)

^m

C-regular fractions in

( _Ω

_p

)

^sm

C-regular fractions

in [3 levels - 4 factors]

(GF[

^ps

])

^m

GF-regular fractions in [9 levels - 2 factors]

[9 levels - 2 factors]

Notations

• D: the full factorial design with complex coding D = Ω^m_n

L: the full factorial design with integer coding L = Z^m_n

L is also the exponent set of all the interactions α, β, . . .: the elements of L:

L = ⁿα = (α₁, . . . , α_m) : α_j = 0, . . . , n − 1, j = 1, . . . , m^o

• X_i: a factor

X^α = X₁^α1 · · · X_m^αm interactions or simple factors

Full factorial design and fractions

The full factorial design D, as a subset of C^m, is defined by the system of equations

X_jⁿ − 1 = 0 for j = 1, . . . , m

A fraction is a subset of a full factorial design, F ⊂ D.

It is obtained by adding equations (generating equations) to restrict the set of solutions.

Indicator function F of a fraction F

It is a response defined on the full factorial design D such that F (ζ) =







1 if ζ ∈ F

0 if ζ ∈ D r _F It is represented as polynomial as:

F = ^X

α∈L

b_αX^α(ζ) ζ ∈ D

Important statistical features of the fraction can be read out from the form of the polynomial representation of the indicator function.

C -regular fractions

• F a fraction without replicates where all factors have n levels

• Ωn the set of the n-th roots of the unity, Ω_n = {ω0, . . . , ωn−1}

• L a subset of exponents, L ⊂ L = (Z_n)^m containing (0, . . . , 0), l = #L

• e a map from L to Ωn, e : L → Ω_n

A fraction F is regular if:

1. L is a sub-group of L,

2. e is a homomorphism, e([α + β]) = e(α) e(β) for each α, β ∈ L,

3. the defining equations are of the form

X^α = e(α) , α ∈ L

If H is a minimal generator of the group L, then the equations X^α = e(α) with α ∈ H ⊂ L are called minimal generating equations.

• We consider the general case where e(α) can be different from 1

• We have no restriction on the number of levels

A necessary condition is the e(α)’s must belong to the subgroup spanned by the values X^α.

For example for n = 6 an equation like X₁³X₂³ = ω₂ can not be a defining equation.

w₂

w₀ w₁

w₃

w5

w4

w2

w₀ w₁

w₃

w

5

w

4

Subgroup spanned by: X_i² X_i³

Example 1: A regular fraction of a 3⁴ design



























A B C D

0 0 0 0

0 1 1 1

0 2 2 2

1 0 1 2

1 1 2 1

1 2 0 1

2 0 2 1

2 1 0 2

2 2 1 0





















































X1 X2 X3 X4

1 1 1 1

1 ω1 ω1 ω1

1 ω2 ω2 ω2

ω1 1 ω1 ω2

ω1 ω1 ω2 1 ω1 ω2 1 ω1

ω2 1 ω2 ω1

ω2 ω1 1 ω2

ω2 ω2 ω1 1



























The complex fraction is defined by

X_j³ − 1 = 0 , j = 1, . . . , 4 together with the generating equations

X₁X₂X₃² = 1 and X₁X₂²X₄ = 1 . Then: H = {(1, 1, 2, 0), (1, 2, 0, 1)}

e(1, 1, 2, 0) = e(1, 2, 0, 1) = ω₀ = 1

L = {(0, 0, 0, 0), (0, 1, 1, 2), (0, 2, 2, 1), (1, 1, 2, 0),

(2, 2, 1, 0), (1, 2, 0, 1), (2, 1, 0, 2), (1, 0, 1, 1), (2, 0, 2, 2)}.

Indicator function and regular fractions

(Pistone, Rogantin, 2005)

The following statements are equivalent:

1. The fraction F is regular according to previous definition with defining equations X^α = e(α), α ∈ L

2. The indicator function of the fraction has the form F (ζ) = 1

l

X α∈L

e(α) X^α(ζ) ζ ∈ D

where L is a given subset of L and e : L → Ω_n is a given mapping.

3. For each α, β ∈ L the parametric functions represented on F by the terms X^α and X^β are either orthogonal or totally aliased

Example 1 (continued): A regular fraction of a 3⁴ design

The indicator function is:

F = 1

9

1 + X₂X₃X₄ + X₂²X₃²X₄² + X₁X₂X₃² + X₁²X₂²X₃ +X₁X₂²X₄ + X₁²X₂X₄² + X₁X₃X₄² + X₁²X₃²X₄^

Example 2: a regular fraction of a 6³ design The terms X^α take values in Ω₆ or one of the two subgroups {1, ω₃} and {1, ω₂, ω₄}.

The generating equations of the fraction are X₁³X₃³ = ω₃ and X₂⁴X₂⁴X₃² = ω₂

w2

w0

w1

w3

w

5

w

4

(subgroups – laterals)

Then: H = {(3, 0, 3), (4, 4, 2)}

e(3, 0, 3) = ω₃, e(4, 2, 2) = ω₂

L = {(0, 0, 0), (3, 0, 3), (4, 4, 2), (2, 4, 4), (1, 4, 5), (5, 2, 1)}.

The full factorial design has 216 points and the fraction has 36 points The indicator function is:

F = 1

6 1 + ω3X₁³X₃³ + ω4X₁⁴X₂⁴X₃² + ω2X₁²X₂²X₃⁴ + ω1X1X₂⁴X₃⁵ + ω5X₁⁵X₂²X3

C -regularity under permutation of levels.

A C-regular fraction is transformed into a C-regular fraction when a level permutation of the following type is performed on one or more factors:

1. Cyclical permutations on the factor X_j:

(ζ₁, . . . , ζ_j, . . . , ζ_m) 7→ (ζ₁, . . . ,ω_kζ_j, . . . , ζ_m) k = 0, . . . , n_j − 1 All the n level cyclical permutations are obtained in this way.

2. If n_j is a prime number, permutations on the factor X_j: (ζ₁, . . . , ζ_j, . . . , ζ_m) 7→ (ζ₁, . . . , ω_kζ_j^h, . . . , ζ_m) . with k = 0, . . . , n_j − 1 and h = 1, . . . , n_j − 1.

In this way a sub-group of permutation of order n_j(n_j− 1) is obtained.

If n = 2 or n = 3 all the level permutations are of type 2.

Example 1 (continued): A regular fraction of a 3⁴ design

We permute the levels ω₀ and ω₁ of the last factor X₄ using the trans- formation:

(ζ₁, ζ₂, ζ₃,ζ₄) 7→ (ζ₁, ζ₂, ζ₃, ω₁ζ₄²) .

The indicator function of the transformed fraction is:

F = 1

9

1 + ω₁X₂X₃X₄² + ω₂X₂²X₃²X₄ + X₁X₂X₃² + X₁²X₂²X₃ +ω₁X₁X₂²X₄² + ω₂X₁²X₂X₄ + ω₂X₁X₃X₄ + ω₁X₁²X₃²X₄^2 . Then it is a regular fraction.

The generating equations of the transformed fraction are:

X₁X₂X₃² = 1 and X₁X₂²X₄² = ω₂ .

Regular fractions in Galois Field theory

for p

^s

levels

Let G be a fraction generated by the following equations in [GF (p^s)]^m:

m X j=1

a_ijz_j = b_i i = 1, . . . , r a_ij, z_j, b_i ∈ GF (p^s)

g irreducible polynomial such that GF (p^s) is isomorphic to the field Z_p[x]/ < g(x) >

Example: GF(2²)

The Galois Field GF(2²) can be represented as the field of equivalence classes mod x² + x + 1 of polynomials of degree 1 whose coefficients belong to Z_2:

GF(2²) ∋ z −→ z₀ + z₁x z₀, z₁ ∈ Z₂ Polynomial representation of GF(2²): {0, 1, x, 1 + x}.

GF-regular and ^C -regular fractions for p ^s levels

Recoding of each factor:

GF (p^s) ∋ z = z₀ + z₁x + · · · + z_s−1x^s−1 −→ (ω^z0, ω^z1, . . . , ω^zs−1) ∈ (Ω_p)^s The GF-regular fraction G is mapped onto a C-regular fraction F

F has s × m factors: each original factor splits into s pseudo-factors

G F

GF-regular fractions in

[4 levels - 2 factors]

[9 levels - 2 factors]

(GF[ p ])^{s m}

C-regular fractions in

[2 levels - 4 factors]

[3 levels - 4 factors]

Ω

_p

( )

^sm

Not all C-regular fractions in the pseudo-factors correspond to GF-regular fractions. Special conditions have to be assumed.

Example: GF-regular fractions with n = 2²

Regular fractions in GF(2²) generated by:

a₁z₁ + a₂z₂ = 0 a₁, a₂, z₁, z₂ ∈ GF(2²)

(a₁₀ + a₁₁x)(z₁₀ + z₁₁x) + (a₂₀ + a₂₁x)(z₂₀ + z₂₁x) = 0 mod (x² + x + 1) a_ij ∈ Z₂ Generating equations in the pseudo-factors with levels in Ω₂:

X₁₀^a10X₁₁^a11X₂₀^a20X₂₁^a21 = 1 X₁₀^a11X₁₁^a10+a11X₂₀^a21X₂₁^a20+a21 = 1

There are two inequivalent fractions:

G1 :





Z1 Z2

1 + x 1 + x

1 1

x x

0 0



 F1 :





X10 X11 X20 X21

−1 −1 −1 −1

−1 1 −1 1

1 −1 1 −1

1 1 1 1



 F1 = 1 4 + 1

4X10X20 + 1

4X11X21+ 1

4X10X11X21X20

G2 :





Z1 Z2

1 + x x 1 1 + x

x 1

0 0



 F2 :





X10 X11 X20 X21

−1 −1 1 −1

−1 1 −1 −1 1 −1 −1 1

1 1 1 1



 F2 = 1 4 + 1

4X10X21 + 1

4X11X20X21+ 1

4X10X11X20

Pseudo factors for C -regular fractions

A regular fraction S with m factors and p^s levels can be transformed in a regular fraction F with s × m factors where each original factor splits into s pseudo-factors. The generating equations are transformed by the map

Ω_p^s ∋ Y_j = X_j0X_j1^(1/p)X_j2^(1/p)2 · · · X_js−1^(1/p)(s−1) ∈ (Ω_p)^s

C-regular fractions in

[4 levels - 2 factors]

[9 levels - 2 factors]

Ω

_p

( )

^m

C-regular fractions in

[2 levels - 4 factors]

[3 levels - 4 factors]

Ω

_p

( )

^{sm s}

F S

Example:

C-regular fractions in [Ω₄]² splitting in C-regular fractions in [Ω₂]⁴ with generating equations of the form

Y ^α = 1

all C-r.f. in [Ω₄]² special C-r.f. in [Ω₂]⁴ [GF (4)]² S₁ : Y₁Y₂ = 1 X₁₀X₂₀ = 1 X₁₀X₁₁X₂₁ = 1

S₂ : Y₁Y₂² = 1 X₁₀X₂₀ = 1 X₁₁X₂₂ = 1

S₃ : Y₁Y₂³ = 1 F₁: X₁₀X₂₀ = 1 X₁₁X₂₂ = 1 G₁ S₄ : Y₁²Y₂² = 1 X₁₀X₂₀ = 1

F₂: X₁₀X₂₁ = 1 X₁₁X₂₀X₂₁ = 1 G₂ Only S₃ corresponds to a GF–regular fraction, G₁

The GF–regular fraction G₂ does not correspond to any S_i

Discussion

1. The definition of C-regular fractions applies to asymmetric case.

2. A fraction is C_-regular if and only if the complex interactions have the non partial aliasing property.

3. Proposition about C-regular fractions provides an algorithmic way to check if a given array is a regular fraction.

4. If the number of levels is:

•

p

^{prime: Z}p-regular fractions are C-regular fractions and vicev- ersa.

•

p

^s: GF-regular fractions are C-regular fractions in the pseudo- factors but the converse is false.