Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.
|
|
|
|
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).
|
|
|
|
