Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Mathematical Programming (Optimization) and the Number Theory
Replies: 0

 Yuly Shipilevsky Posts: 17 Registered: 1/25/05
Mathematical Programming (Optimization) and the Number Theory
Posted: Mar 21, 2009 3:28 PM

Yuly Shipilevsky

Mathematical Programming (Optimization) and the Number Theory: Minimum Principles.

http://www.geocities.com/yulysh2000/techie.html

Restricted Common Multiples (RCM), Restricted Least Common Multiple(RLCM), Restricted Greatest Common Multiple(RGCM).

The following generalization of LCM
(Least Common Multiple) of M numbers
X1, . . . , XM : Restricted ( or Conditional)
Least Common Multiple (RLCM)

Instead of consideration of complete set of
multiplyers
N = { 1 , 2 , 3 , . . . }, let us
consider a set A of M subsets of set N :

A = { N1 , . . . , NM |
Ni is a subset of N,
i = 1 , . . . , M }

Let us define a Restricted LCM (RLCM)for M numbers
X1, . . . , XM as their LCM under restriction that
multiplyers for each Xi are taken from a subset Ni[Xi]
of set N:

RLCM( X1 , . . . , XM | A ) =

RLCM( X1 , . . . , XM |
N1[X1] , . . . , NM[XM] ) =

LCM ( X1 , . . . , XM |
N1[X1] , . . . , NM[XM] ) .

For example, it is reasonable to consider

RLCM ( 14 , 17 | N1[14] , N2[17] ) ,

N1[14] = { a[n] = n! , n= 1, . . . } ,
N2[17] = { b[n] = n(n+1) , n= 1, . . . } , or, e.g.:

N1[14] = { n : 100 < n <1000} ,
N2[17] = {n : n >= 2000}

Actually, the set A can be defined as a finite or infinite
matrix.

If at least one subset Ni of mask A has finite cardinality,
then either both: Restricted Least Common Multiple (RLCM) and Restricted Greatest Common Multiple (RGCM) don't exist or both: RLCM and RGCM
do exist (RGCM >= RCM >= RLCM).

It would be interesting to develop methods for
RLCM, RGCM computing for any mask(matrices) A.

In a more general scheme, multiplyers mi
(for each Xi) are not supposed to be
independant, but supposed to belong to
some subset S_N^M of a Cartesian product N^M.

It (the subset S_N^M) can be defined, e.g., as multiplayers mi,
satisfied to a set of K constraints:

f1(m1 , . . . , mM) >= 0
. . . . . . . . . . .
fK(m1 , . . . , mM) >= 0

Reducing of RCM's computing to the solution of a Mathematical Programming
(Optimization) problem.

If a M-tucle m=(m1 , . . . , mM) is contained in S_N^M, and said M-tucle m corresponds to some
Common Multiple CM of a M-tucle
X=(X1, ... , XM) then:

(1) CM= m1*X1 = ... = mM*XM

Let's define the following functions:

(2) S1(m,X) = SUM_i,j=1...M,i>j[miXi - mjXj]^2

(3) S2(m,X) = SUM_i=1...M
[s - miXi]^2

wherein:

s = (m,X)/M = [SUM_i=1...M(miXi)]/M,

(m,X) is a scalar product of m and X.

Proposition 1
(Minimum Principle).

If m0 contained in S_N^M and
m0 corresponds to some Restricted Common Multiple of X, then:

S1(m0,X) = S2(m0,X) = 0 ,

S1(m,X) > =0, S2(m,X) >= 0,

for any
M-tucle m contained in S_N^M,

and:

min_m { S1(m,X) | S_N^M } = min_m { S2(m,X) | S_N^M } =
S1(m0,X) = S2(m0,X) = 0,

- the minimums among all m
contaned in S_N^M.

Proof.

It follows from (1) , (2) and (3).

On the base of Proposition 1 we can suggest a

Conjecture 1.

To compute all multiplyers
(and therefore all Restricted Common Multiples), contained in S_N^M that correspond to the respective Restricted Common Multiples of X do:

(a) Find M-tucles m contained in S_N^M and minimizing S1 or S2
(S1 -> min | S_N^M) or
(S2 -> min | S_N^M)

(b) Select M-tucles m found at step (a) that satisfied condition (1).

Reducing of RLCM's computing to the solution of a Mathematical Programming (Optimization) problem.

Let's define the following functions:

(4) S3(m,X) = SUM_i,j=1...M,i>j[miXi - mjXj]^2 + mkXk , (k=1...M)

(5) S4(m,X) = SUM_i=1...M
[s - miXi]^2 + mkXk , (k=1...M)

wherein:

s = (m,X)/M = [SUM_i=1...M(miXi)]/M,

(m,X) is a scalar product of m and X.

Proposition 2
(Minimum Principle).

If m0 contained in S_N^M and
m0 corresponds to the Restricted Least Common Multiple of X, then:

S3(m0,X) = S4(m0,X) = RLCM(X | S_N^M) ,

and:

min_m { S3(m,X) | S_N^M } = min_m { S4(m,X) | S_N^M } =
RLCM(X | S_N^M) ,

- the minimums among all m
contaned in S_N^M.

Proof.

It follows from (1) , (4) and (5).

On the base of Proposition 1 we can suggest a

Conjecture 2.

To compute a multiplyer, contained in S_N^M that corresponds to the respective Restricted Least Common Multiple of X do:

(a) Find M-tucle m0 contained in S_N^M and minimizing S3 or S4
(S3 -> min | S_N^M) , or
(S4 -> min | S_N^M)

(b) Check that M-tucle m0 found at step (a) satisfied condition (1).

Reducing of RGCM's computing to the solution of a Mathematical Programming (Optimization) problem.

Let's define the following functions:

(6) S5(m,X) = SUM_i,j=1...M,i>j[miXi - mjXj]^2 - mkXk , (k=1...M)

(7) S6(m,X) = SUM_i=1...M
[s - miXi]^2 - mkXk , (k=1...M)

wherein:

s = (m,X)/M = [SUM_i=1...M(miXi)]/M,

(m,X) is a scalar product of m and X.

Proposition 3
(Minimum Principle).

If m0 contained in S_N^M and
m0 corresponds to the Restricted Greatest Common Multiple of X, then:

-S5(m0,X) = -S6(m0,X) = RGCM(X | S_N^M) ,

and:

min_m { S5(m,X) | S_N^M } = min_m { S6(m,X) | S_N^M } =
-RGCM(X | S_N^M) ,

- the minimums among all m
contaned in S_N^M.

Proof.

It follows from (1) , (6) and (7).

On the base of Proposition 3 we can suggest a

Conjecture 3.

To compute a multiplyer, contained in S_N^M that corresponds to the respective Restricted Greatest Common Multiple of X do:

(a) Find M-tucle m0 contained in S_N^M and minimizing S5 or S6
(S5 -> min | S_N^M) , or
(S6 -> min | S_N^M)

(b) Check that M-tucle m0 found at step (a) satisfied condition (1).