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 Mtucle m=(m1 , . . . , mM) is contained in S_N^M, and said Mtucle m corresponds to some Common Multiple CM of a Mtucle 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 Mtucle 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 Mtucles m contained in S_N^M and minimizing S1 or S2 (S1 > min  S_N^M) or (S2 > min  S_N^M)
(b) Select Mtucles 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 Mtucle 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 Mtucle 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 Mtucle 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 Mtucle m0 found at step (a) satisfied condition (1).



