Ñàéò Èíôîðìàöèîííûõ Òåõíîëîãèé

CausEs of APPEARING uncertainty in decisions of COMBINATORIal and NUMBER–THEOREtic DATA analysis problems

Y.V. Chebrakov, V.V. Shmagin

St-Petersburg Technical University, 195251, St-Petersburg, Politehnicheskaya 29, Russia

e-mail: chebra@phdeg.hop.stu.neva.ru

Àííîòàöèÿ – Èññëåäóåòñÿ ðÿä òåîðåòèêî-÷èñëîâûõ è êîìáèíàòîðíûõ çàäà÷ àíàëèçà äàííûõ íà ïðåäìåò ñóùåñòâîâàíèÿ äëÿ íèõ ðàçëè÷íûõ àíàëèòè÷åñêèõ ðåøåíèé. Äåìîíñòðèðóåòñÿ, ÷òî (à) îñíîâíîé ïðè÷èíîé ïîÿâëåíèÿ íåîäíîçíà÷íûõ ðåçóëüòàòîâ êîëè÷åñòâåííîé îáðàáîòêè ìàññèâîâ äàííûõ, ñîäåðæàùèõ ñòðîãî äåòåðìèíèðîâàííûå öåëûå ÷èñëà, ÿâëÿåòñÿ èçíà÷àëüíàÿ íåîïðåäåëåííîñòü ïîñòàíîâîê óêàçàííûõ çàäà÷; (á) â íåêîòîðûõ ñëó÷àÿõ êîìïàêòíîå îáùåå àíàëèòè÷åñêîå ðåøåíèå óêàçàííûõ çàäà÷ ìîæíî ïîëó÷èòü òîëüêî ñ ïîìîùüþ ìåòîäîâ îïåðàöèîíàëüíîãî (íåïðåðûâíîãî) âàðèàíòà òåîðèè ðåãðåññèîííîãî àíàëèçà.

1. Introduction

It is well-known, that the application of fitting techniques is required for solving a set of problems on quantitative processing numerical information. However, as it is demonstrated in [1 – 3], the application of available fitting techniques leads to arising series of theoretical and computative difficulties, which are mainly explained by the fact that modern statements of data analysis problems are too far from real experimental situations. In particular, up to the present these statements make no allowance for facts that

– results of calculations may be depended on the way, by which the investigated data are obtained;

– the given accuracy of calculated values is not to be computed for data, measured with high level of errors;

– a single solution of the data analysis problems for contaminated data arrays is wrong one; and others.

From our opinion [2, 3], to bypass series of the mentioned difficulties, it is necessary to replace the classical (discrete) approach to quantitative processing numerical information by more progressive operational (continuous) one, which is based on the following set of computative methods:

– virtual device (VD) method, allowing to determine the contamination level of analysing data array;

– equivalent analytical formulae (EAF) method, allowing for given approximative functions to construct equivalent analytical formulae, in which the values of the vector parameter depend continuously on some variable;

– method, determining exact values of bounds for the possible varying of the vector parameter values in the approximative functions, etc.

In this work some integer data arrays are investigated and it is demonstrated, if analysing arrays contain only integer numbers, then the main cause of appearing uncertainty in decisions of data analysis problems is a fontal uncertainty incident to statements of these problems (see Sect. 2 and 3). It is also stated (see Sect. 3)

– although combinatorial and number-theoretical analytical formulae, found by data analysis methods, are correct only inside of investigated intervals, it is sometimes possible to prove their correctness beyond the investigated intervals;

– using only classical methods of data analysis theory leads to a partial loss of numerical solutions of some combinatorial and number-theoretical data analysis problems;

– to find complete analytical solutions of discussed problems it is necessary to use methods of the continuous variant of the estimation theory.

2. Different analytical decisions of one combinatorial problem on constructing Magic squares

We remind  that in the general case [3 – 5]  Magic squares represent by themselves numerical or analytical square tables, whose elements satisfy a set of definite basic and additional relations. The basic relations therewith assign some constant property for the elements located in the rows, columns and two main diagonals of a square table, and additional relations, assign additional characteristics for some other sets of its elements. In particular, when the constant property is a significance of sum of various elements in rows, columns or main diagonals of the square, then this square is an Additive one. If an Additive square is composed of successive natural numbers from 1 to n2, then it is a Classical one.

For any linear algorithmic methods of constructing Classical squares of odd orders, the functions f and g have the following forms [3 – 6]:

f(N, n) ? a1(N1) +b1[(N1)/n] +c1,

(1)

g(N, n) ? a2(N1) +b2[(N1)/n] +c2,

where f and g are such functions, which permit to compute the position for any natural number N from 1 to n2 in cells of Classical square: x = f(N, n) and y = g(N, n); square brackets mean the integer part; a sign “? ” is the modulo n equality; N is any natural number from 1 to n2; a1, b1, c1 and a2, b2, c2 are such integral coefficients, that the numbers a1, a2, b1, b2; a1b2a2b1; a2 – a1, b2b1, a2 + a1 and b2 + b1 are mutually disjoint with n.

It should be noted, that the above conditions for coefficients of functions f and g become contradictory for even n. For example, by the conditions, the coefficients a1, a2, b1 and b2 of the functions f and g of (1) should be mutually disjoint with n, and consequently, if n is even, they must be odd. The same requirement must be the true for the number d = a1b2a2b1. But if a1, a2, b1 and b2 are odd, the number d, which is the difference of the two odd numbers, will be an even number.

Thus, an essential fault of linear formulae of (1) is the impossibility of using them for constructing Classical squares of even orders.

Proposition 1 If a Classical square of the n-th order is constructed by formulae (1), then it may be constructed also by the formula

N(x, y) = n p(x, y) + r (x, y) + 1,

(2)

where p(x, y) ? a 1 x + b 1 y + s 1 and r (x, y) ? a 2 x + b 2 y + s 2.

Proof. The equivalence of formulae (1) and (2) appears from their linearity and the fact, that (2) are inverse formulae to (1).

We remind [3 – 7] that, a quadratic table n? n in size is Latin square of n-th order if only n elements of this table are different and each of these n elements occurs only one time in each row and column of the table. The two Latin squares P and R of the same order n are called orthogonal if all the pairs, formed by their elements pi j and ri j (i is the number of a row; j is the number of a column) are different.

Proposition 2. If elements of a Latin square of the n-th order are numbers 0, 1, …, n  1, then, for constructing such Latin square, one may use a linear comparison

L(x, y) ? a x + b y + s ,

(3)

where a and b are integer numbers, which are to be mutually disjoint with n; s is any integer number.

Proof. Let the numbers L(x, y) of (3) are located in each cells of a quadratic table n? n in size. We consider n numbers, which are located in row y0 of this table. Since the discussed numbers are obtained from the linear comparison (3) at x = 0, 1, …, n 1, to show that all they are different, we should demonstrate that they belong to different modulo n classes. Let x1 > x2 and a x1 + b  y0 + s ? a x2 b  y0 + s . Since b  ys is a constant, in accordance with the properties of comparisons [8], we obtain the new equality a x1 ? a x2. Hence, since a is mutually disjoint with n, x1 ? x2. But this equality contradicts our assumption. Thus, each of numbers 0, 1, …, n 1 occurs only one time in each row and column of the discussed table and so this table is Latin square of n-th order.

Proposition  3 Every Classical square of the odd order, decomposed on two orthogonal Latin squares, may be constructed by the formulae (1) and otherwise.

Proof. The truth of Proposition 3 follows directly from Propositions 1 and 2 and conditions for coefficients of functions f and g of (1).

Determination. A quadratic table n? n in size is the generalised Latin square of n-th order if only n elements of this table are different and each of these n elements occurs only n times in this table.

Proposition  4. Every Classical square of an order n may be decomposed on two orthogonal generalised Latin squares p and r of the order n.

Proof. To prove Proposition 4, it is sufficient to note that

a) any integer number N from 1 to n2 may be presented in the form

N = n p + + 1,

(4)

where p and r can take values only 0, 1, …, n –1;

b) each of values 0, 1, …, n –1 of parameters p and r occurs n times precisely in the decomposition (4) of numbers N.

Thus, to construct two orthogonal generalised Latin squares p and r from a Classical square of a order n, one should replace in the Classical square all numbers N by respectively (– 1) mod n and [(– 1) / n].

Proposition 5. Every Classical square of order n may be constructed by the formula (2), in which functions p(x, y) and r(x, y) may belong, in general case, to both linear and non-linear classes of ones.

Proof. The truth of Proposition 5 follows directly from Propositions 4 and conditions for coefficients of (1).

We note, in particular, one may construct Classical squares of even-even orders n (n = 4k; k = 1, 2, …) by the analytical formula (2), in which functions p(x, y) and r(x, y) have the following forms [3 – 5]

p(x, y) = c + (1– c) (n – – 1),

(5)

r(x, y) = (1 – c) y + c (– – 1),

where c = {[(x+1)/2]+[(y+1)/2]} mod 2; or

p(x, y) = cd – x – 1 + (1 – c) (n d),

(6)

r (x, y) = by + (1 – b) (ny – 1),

where c = (x + y + a) mod 2; d = (1 – a) y + a (ny – 1); b = {[(x+3)/2] + [ y/2] + a} mod 2; a = [2y/n]; and so on.

Proposition 7. If a Classical square of the n-th order is constructed by formulae (1), then it may be constructed also by the formula

N(x, y) ? a + b l c,

(7)

where a, b and c are any integer numbers; l is 0 or 1, the sign “? ” is the modulo n2 equality.

Proof. Let a Classical square of an odd order be constructed by formulae (1). It follows from Proposition 1 that this square may be constructed also by formulae (2). We deduct x-th element of first row from every x-th element of all y-th rows of the Classical square. It is evident that the number

a n{(a 1 x + b 1 y + s 1) mod n} –

(8)

n{(a 1 x + s 1) mod n} +

(a 2 x + b 2 y + s 2) mod n

(a 2 x + s 2) mod n n mod n2

will be located in the cell (x, y) of the reformed Classical square {see (2)}. Using the equality (dn) mod n2 = n (d mod n) we present (8) as the sum of two summands

n{(b 1 y)} mod n + {(a 2 x +b 2 y +

(9)

s 2) mod n – (a 2 x + s 2) mod n}.

The second summand of (9) may have only two values: (b 2 y) mod n or n – (b 2 y) mod n. Thus, we obtain that numbers of any y-th row of the reformed Classical square may have only two values. By using the mentioned method of constructing formula (7), we find that parameters of this formula a, b, c and l are connected with parameters of the formula (2) by correlations

a=n{(a 1x+s 1) mod n}+

(10)

(a 2x+s 2) mod n, b=n{(b 1 y) mod n}

+b 2 y) mod n, l = [1– sign{(a 2x +

b 2y+s 2) mod n

–(a 2x+s 2) mod n} ]/2, c = n,

where sign(x) = c x? /x if x ? 0 and sign(0) = 0.

3 Different representations of an analytical formula for counting Magic squares 3? 3 from natural numbers

As generally known [9], polynomial-shaped dependences are widely used in number theory and combinatorics. These dependences may be formed from the sum of usual multinomial Pm(B, x) = b0+b1x+ …+bmxm and some additional terms containing a set of the following symbols: [x] is the integral part of x; x mod q is x modulo q; etc. In this section we demonstrate that expressions for the polynomial-shaped dependences may be significantly simplified by regression analysis methods. Namely, discussed dependences may be described by functions g{Pm(B? , x)}, where g{x} means the nearest integer to x and B? is some value of multinomial vector parameter B.

Proposition 8. Let A(k) be the general number of different magic squares 3? 3 with 9 distinct natural numbers and a number k in its central cell. Then there are 3 equivalent expressions for computing values of A(k):

(i) A(k) = 9[k/6]2+{3 (k mod 6)

(11)

8}[k/6]+2 2 [{(k mod 6)

+ 5}/6] +[( k mod 6)/5];

(ii) A(k)= g{(3k2–16k +18.5)/12};

(iii) A(k)= g{(3k2–16k +18.5+

0.5x )/12},

where k > 4 and –1<x < 1.

Proof. The correctness of the expression (i) has proven in [5]. Let us prove the correctness of the expression (ii).

We assume, for example, that k=5, 6, …, 34 and make an array {yk, xk}, where xk = k, yk = A(xk) and the value of A(xk) is computed by the expression (i). Analysing the array {yk, xk} by least of squares method (classical regression analysis method) we can compute that, for the multinomial P2(B, x), B? » (0.2500; –1.3330; 1.5467). Then 12B? » (3; –16; 18.5) or A(k) » g{(3k2–16k +18.5)/12}. By analysing the obtained formula for A(k), we find that A(k)= g{(3k2–16k +18.5)/12} for k=5, 6, …, 34.

Let us suppose that the difference D (k) = P2(B? , k ) – A(k) is the periodic function or, in other words, there exists such k0 > 0 that D (k) = D (k+ lk0) for any natural k and l. To prove the correctness of the expression (ii) in this case, it is enough determine the value of k0 and examine the fact that, if values of A(k) are calculated for k = 1, 2, … , k0, then computation results are same as ones calculated from formula (i). To finish the proof it remains for us to say that indeed  D (k) is the periodic function with k0 = 6: if k = 6i+q then

g{(3k2–16k +18.5)/12}= 9i2 + 3iq

(12)

8i + g{3q2 – 16q + 18.5)/12},

where i =1, 2, … ; q = 0, 1, … , 5.

We add that (a) the correctness of the expression (iii) is proved in the same manner as the correctness of the expression (ii); (b) the expression (iii) is evident only if investigator works in the frame of the continuous approach to quantitative processing numerical information (see Introduction).

References

[1] Chebrakov Y V  Computative paradoxes in regresion analysis of contaminated data arrays In: Proc. of 3rd Workshop on Simulation (St.-Petersburg, 1998) 248-253

Chebrakov Y V and Shmagin V V Uncertainty in decisions of regression analysis problems In: Proc. of Intern. Conf. on Soft Computing and Measure (St.–Petersburg, 1998) 1 186-189

Computative paradoxes in modern data analysis Smarandache Notions J. (1999) 10 (1-2-3) 61-80

Data analysis methods for processing results of measurement experiments with heterogeneous objects In: Proc. of Intern. Conf. on Soft Computing and Measure (St.–Petersburg, 1999 2  20-24

[2] Chebrakov  Y V The parameters estimation theory in the measuring experiments (St. Petersburg, St. Petersburg State Technical Univ. Press, 1997) (In Russian)

System analysis methods in experimental inquiry (St. Petersburg, St. Petersburg State Technical Univ. Press, 1997) (In Russian)

Chebrakov Y V and Shmagin V V Correct solutions of fit problems in different experimental situations In: Advanced Mathematical Tools in Metrology III /Ciarlini P., Cox M.J., Pavese F. and Richter D. (eds.) (Singapore: World Scientific, 1997) 246-249

Some nontraditional approaches to solving a few data analysis problems In: Integral methods in science and engineering / C.Constanda, J.Saranen and S.Seikkala (eds.) (Edinburgh: Longman, 1997) 2 69-73

Finding the best linear-multiple model in the case of microstatistics In: Proc. of Intern. Conf. on Approximation and Optimization (Cluj-Napoca, 1997) 2 41-46

Regression data analysis for physicists and chemists (St.–Petersburg State University Press, St.–Petersburg, 1998) (In English)

[3] Chebrakov  Y V System analysis methods in experimental inquiry (St. Petersburg, St. Petersburg State Technical Univ. Press, 1997) (In Russian)

[4] Chebrakov  Y V Analytical formulae and algorithms for constructing Magic squares from an arbitrary set of 16 numbers Smarandache Notions J. (1997) 8 (1-2-3) 184-201

Chebrakov  Y V and  Shmagin V V  Different types of formulae for the analytical description of Magic squares constructing methods In: Proc. of Conf. on Analytic and Elementary Number Theory (Vienna, 1996) 200-203

Analytical approach to description of some combinatorial and number-theoretic computative algorithms Smarandache Notions J. (2000) 11 (1-2-3) 156-164

[5] Chebrakov  Y V Magic squares. Number theory, algebra, combinatorial analysis (St. Petersburg, St. Petersburg State Technical Univ. Press, 1998) (In Russian)

Advance of Smarandache approach to solving systems of Diophantine equations Smarandache Notions J. (2000) 11 (1-2-3) 144-155

[6] Postnikov  M M  Magic squares (Moscow, Nauka, 1964) (In Russian)

[7] Denes  J and  Keedwell  A D  Latin Squares: New Developments in the Theory and Applications (Amsterdam, North-Holland, 1991)

[8] Vinogradov I M Foundation of the theory of numbers (Moscow, Nauka, 1981) (In Russian)

[9] Hall M Combinatorial theory (Waltham, Blaisdell, 1967)

Riordan J An introduction to combinatorial analysis (New York, John Wiley, 1958)


Site of Information Technologies
Designed by  inftech@webservis.ru.