1.6 Paul Erd¨ os và các phân số Ai Cập
1.6.4 Thêm các bài toán từ bài toán cũ, mới và kết quả
2b+ 1 có thể được biểu diễn bằng tổng hữu hạn có dạng P
k
1
2qk+ 1. Câu hỏi cũ của Stein hỏi nếu phân tích như vậy có thể luôn luôn làm được bởi thuật toán tham lam. Nói cách khác, nếu chúng ta bắt đầu với một số hữu tỉ dương tùy ý a
2b+ 1 và lặp đi lặp lại trừ phân số đơn vị lớn 1
2q+ 1 sao cho phần còn lại là không âm, quá trình này phải luôn luôn chấm dứt? Ví dụ không được biết mà có thể chứng minh không chấm dứt, mặc dù có chấm dứt lý do mà các mẫu số trở lên rất lớn. Ví dụ, bắt đầu với
5
1444613, thuật toán tham lam tạo ra 37 số hạng mới chấm dứt, với mẫu số lớn nhất có 384122451172 chữ số thập phân. Ta biết rằng một số hữu tỉ dương a
b có thể được biểu diễn bằng một tổng hữu hạn của các phân số có dạng 1
pk+q nếu
và chỉ nếu
b
(b,(p, q)), p (p, q)
= 1. Người ta có thể hỏi ở đây liệu các thuật toán tham lam cũng luôn luôn chấm dứt cho biểu diễn này. Thậm chí để hạn chế các mẫu số nhiều hơn, tác giả đã cho thấy rằng điều kiện cần và đủ để số hữu tỷ a b có thể được biểu diễn là
a b = 1
x21 + 1
x22 +ã ã ã+ 1
x2k với cỏc số nguyờn dương0< x1 < x2 <ã ã ã< xk,
là a
b =∈
0,π2
6 −1
∪
1,π2 6
. Ví dụ 1.11.
1 2 = 1
22 + 1 32 + 1
42 + 1 52 + 1
62 + 1
152 + 1 162 + 1
362 + 1
602 + 1 1802.
Tôi tin rằng đó là một điều kiện rất hiếm hoi cho thuật toán tham lam để đạt được kết quả trong tình huống này !
Theo cách này một số câu hỏi được nêu ra bởi Wilf năm 1961 liên quan những gì ông gọi là "Nghịch đảo dựa trên các số nguyên". Bằng cách này ông muốn nói các tập hợp S các số nguyên sao cho mỗi số nguyên dương có thể được biểu diễn như là một tổng hữu hạn các nghịch đảo của các số nguyên lấy từ S.
Ví dụ, Ông hỏi :"Có phải cấp số cộng vô hạn dựa trên một nghịch đảo?";"Phải có một số nghịch đảo dựa trên mật độ dương"
Tổng quát hơn, ta có thể xác định một nghịch đảo dựa vào các số hữu tỉ là một tập hợp S của các số nguyên dương sao cho mỗi số hữu tỉ dương p
q là một tổng hữu hạn hữu hạn các nghịch đảo của các phần tử trong tập hợp S. Hiện nay chúng ta không biết điều kiện cần và đủ cho một tập hợp để được một số nghịch đảo dựa trên các số nguyên hoặc các số hữu tỉ. Tuy nhiên, định lý tổng quát trong phương diện này là như sau.
Cho một tập hợp T = t1, t2,ã ã ã gồm cỏc số nguyờn dương, xỏc định P(T) là tập hợp tất cả các tổng hữu hạn các phần tử được lấy từ T. Ngoài ra, xác định T−1 =
1
ti :ti∈T
. Chúng ta sẽ nói rằngT-là hoàn chỉnh nếu mỗi số nguyên đủ lớn thuộcP(T). Hơn nữa, xỏc địnhM(T)là tập hợp tất cả cỏc tớch sốti1, ti2ã ã ãtir ở đú 1≤i1 < i2<ã ã ã< ir với r= 1,2ã ã ã . Cuối cựng, chỳng ta hóy núi rằng một số thực α là T-có thể biểu diễn được nếu với mọi > 0 có một u ∈ T sao cho 0≤u−α < . Kết quả sau đây thộc về E. J. Graham, 1964.
Định lý 1.22. Giả sử S =s1, s2ã ã ã là dóy cỏc số nguyờn dương thỏa món M(S) là hoàn chỉnh và sn+1
sn
là bị chặn khi n → ∞. Khi đó p
q ∈ P(M(S)−1) với (p, q) = 1 nếu và chỉ nếu p
q là M(S)−1− có thể biểu diễn được và p chia hết cho một vài phần tử của M(S).
Từ sau đó, chẳng hạn, tập hợp gồm các số nguyên tố cùng nhau với nghịch đảo bình phương dựa vào các số hữu tỉ. Ta không biết dù có điều kiện sn+1
sn
bị chặn là cần thiết cho kết luận của định lý nắm giữ.
Một kết quả cổ điển của Curtiss vào năm 1922 khẳng định rằng phép tính xấp xỉ Rn nghiêm ngặt gần nhất của 1 bằng một tổng của n phân số đơn vị là luôn cho bởiRn =Pn
k=1
1
uk+ 1, trong đó un được xác định bằng công thức truy hồi:u1 = 1 và un+1 = un(un+ 1) với n ≥ 1. Lập luận tương tự cũng biết cho các số hữu tỉ có dạng 1
m. Tuy nhiên, nó không nắm giữ cho một vài số hữu tỉ, ví dụ R111
24
= 1
3 trong khi R211 24
= 1 4 + 1
5. Có lẽ đúng là đối với bất kì số hữu tỉ a
b mà nắm giữ cuối cùng. Nói cách khác, đúng là đối với bất kì số hữu tỉ a b phép tính xấp xỉ Rna
b
của a
b nghiêm ngặt gần nhất được cho bởi Rn
a b
=Rn−1 a
b
+ 1 m
trong đó m là mẫu số nhỏ nhất chưa được sử dụng mà Rn a
b
< a
b được chứng minh rằng n là đủ lớn? Trên thực tế cách xử lí này thậm chí phải nắm giữ tất cả các số đại số.
Đối với mỗi n, gọi Xn là kí hiệu cho tập hợp (
x1, x2,ã ã ã , xn :
n
X
k=1
1
xk,0< x1< x2 <ã ã ã< xn
)
và đặtX =∪n≥1Xn. Có nhiều câu hỏi hấp dẫn chưa được giải quyết liên quan đến các mà đã được nêu trong tài liệu này. Sau đây ta sẽ đề cập đến một số câu hỏi trong số đó.
Để bắt đầu, sẽ là thú vị để có công thức tiệm cận hoặc thậm chí ước lượng tốt nhất cho |Xn|. Theo sự hiểu biết của tôi, ước lượng tốt nhất hiện đang được biết đến là :
ec n
3
logn <|Xn|< c(1+)2
n−1
0 ,
trong đó c0 = limn→∞u 1 2n
n = 1.264085ã ã ã , với un được xỏc định như trờn. Cú lẽ chặn dưới có thể được thay thế bằng c20n(1−).
Theo cách xem xét của số lượng lớn các tập hợp trong X, người ta nghi ngờ rằng điều kiện mà nghịch đảo của một tập hợp các số nguyên có tổng bằng 1 không thực sự là một điều kiện rất nghiêm ngặt (một số modul, phần tử lớn nhất không thể là số nguyên tố). Chẳng hạn, nó được nêu bởi R. L. Graham năm 1963 rằng tất cả m ≥78, cú một tập hợp {x1, x2,ã ã ã , xt} ∈ X với Pt
k=1xk = m.
Hơn nữa điều này không đúng cho 77 do D. H. Lehmer phát hiện. Chúng ta giả sử rằng cách xử lý này là đúng phổ biến nhiều hơn. Cụ thể rằng, nó đúng với bất kỡ đa thức p : Z → Z,cú một tập hợp {x1, x2,ã ã ã, xt} ∈ X với Pt
k=1p(xk) = m, cho tất cả m đủ lớn, đưa ra p đáp ứng rõ ràng điều kiện cần:
(i) Hệ số hàng đầu của p là dương;
(ii) gcd(p(1), p(2),ã ã ã)) = 1
Ta biết rằng điều kiện này là đủ để biểu diễn mỗi số nguyên đủ lớn như là một tổng P
aiphân biệtp(ai).
Có bao nhiêu số nguyên xk < n có thể xảy ra như là một phần tử của {x1, x2,ã ã ã , xn} ∈Xn? cú phải là o(n), cnhoặcn−o(n)]?
Số nguyên nhỏ nhất v(n) > 1 mà không xuất hiện như là biến số xk, k,với {x1, x2,ã ã ã , xn} ∈ Xn là gỡ? Dễ thấy rằng v(n) > cn! Nú cú thể là v(n) thực sự tăng lên nhiều hơn như 22
√n hoặc thậm chí 2n(1−).
Kí hiệu kr(n) là số nguyên nhỏ nhất mà không xuất hiện bằng xr trong bất kỡ {x1, x2,ã ã ã , xt} ∈ Xn với x1 < x2 < ã ã ã < xt ≤ n. Nú khụng phải là khú khăn để thấy rằng
k1(n)< cn logn
. Chúng ta không có ý tưởng về giá trị thực sự của kr(n) hoặc thậm chí k1(n). Như một vấn đề liên quan,giả sử chúng ta định nghĩa K(n) là số nguyên nhỏ nhất mà khụng xuất hiện như là xi với bất kỡ i trong bất kỡ {x1, x2,ã ã ã , xt} ∈Xn với x1 < x2<ã ã ã< xt ≤n. Lần nữa cú
K(n)< cn logn
là dễ dàng nhưng hiện nay chúng ta thậm chí không biết nếu k1(n)< K(n).
Có bao nhiêu tập hợp phân biệt Si ∈X,1≤ i≤ k, có thể chúng ta tìm thấy thỏa món Si ⊆ {1,2,ã ã ã , n}?Như chỳ ý của C.Sỏndor , ứng dụng kết quả của định lý 1 lặp đi lặp lại, chúng ta có thể đạt được k = (1 +o(1)) logn. Tổng quát hơn, cú bao nhiờu tập hợp phõn biờt Ti ⊆ {1,2,ã ã ã , n} là thỏa món cú tất cả cỏc tổngP
t∈Ti
1
t là bằng nhau. Bằng cách sử dụng δ-hệ thống mạnh, nó có thể được thông báo rằng, có ít nhất n
ec√logn như vậy. Người ta cũng hỏi có bao nhiêu các tập phõn biệt {x1, x2,ã ã ã , xt} ∈Xn là dương. Nú cú lẽ đỳng là chỉ cú o(logn)tập hợp như vậy.
Thêm một câu hỏi hấp dẫn liên quan đến những gì có thể được gọi là thuộc tính Ram-sey của Xn. Nó đã được hỏi trong một công trình vào 1980 cho dù với bất kỡ phần được phõn chia của {2,3,4ã ã ã } thành vụ hạn phần, một vài phần phải chứa một phần tử của X. Nói cách khác,nếu các số nguyên lớn hơn 1 là tùy ý r-colored,thì ít nhất một trong các lớp màu có chứa hữu hạn tập hợp các số nguyên mà có tổng nghịch đảo bằng 1là đúng? Erd¨os và tôi đã thích bài toán này rất nhiều mà chúng tôi đã đăng một phần thưởng 500 đô-la cho lời giải của mình.Khi nó đưa ra
Một giả thuyết mạnh hơn dóy cỏc số dương cú mật độ cao hơn x1 < x2<ã ã ã chứa một tập con mà có tổng các nghịch đảo bằng 1.Có lẽ điều này có thể được chứng minh nếu chúng ta giả sử rằng xk+1−xkkhác nhau là bị chặn. Nó không đủ để vừa giả sử P
k
1
xk là không bị chặn như là tập hợp của các số nguyên tố đã nêu.Tuy nhiên, có lẽ tổng P
k
1
xk không thể tăng lên nhanh hơn điều này (ví dụ log logn) với xk chắc chắn có dạng x∈X
Cho A(n) kớ hiệu là giỏ trị lớn nhất của |S| thỏa món S⊆ {1,2,ã ã ã, n} khụng là tập hợp chứa trong X. Có lẽA(n) = n−o(n) nhưng điều này vẫn chưa được biết. Một cõu hỏi liờn quan là đõy. Tập hợp nhỏ nhấtS, ⊆ {1,2,ã ã ã , n}mà khụng chứa tập hợp trong X và là lớn nhất trong khía cạnh này là gì? Rất ít được biết đến ở đõy.Tổng quỏt hơn, người ta cú thể hỏi với tập con S∗ ⊆ {1,2,ã ã ã, n} sao cho bất kỡ phần tử phõn biệt s, s1, s2,ã ã ã , sm ⊆S∗, chỳng ta cú 1
s =P
k
1 sk ở đó m > 1 ? Chúng ta chắc chắn có |Sn∗ > cn| như tập hợp n
i: n
2 < i < no
đã nêu.
Liệu có |Sn∗| > cn với c > 1
2? Điều này cú đỳng khụng nếu S ⊆ {1,2,ã ã ã , n} với
|S| > cn thì S chứa x,y,z với 1 x + 1
y = 1
z? Nó được cho thấy bởi Brown và R¨os phiên bản được phân chia của câu hỏi này nắm giữ ví dụ với bất kì cách phân
chia củaZthành vô hạn các lớp phải chứa một lời giải cho 1 x1+ 1
x2+ã ã ã+ 1 xn = 1
z. Có nhiều câu hỏi lý thú chưa được giải quyết mà bao gồm hạn chế các mẫu số của các phần tử trong Sn.Chẳng hạn, Burshtein 1973 cho một ví dụ {x1, x2, cdots, xn} ∈Xn với không có xi chia hết bất kì xj khác.Thậm chí nổi bật hơn, Barbeau 1977 tìm thấy một ví dụ trong đó mỗi xi là tích số của đúng 2 số nguyên tố phân biệt.
Định lý 1.23. Với bất kì >0 có một k() sao cho bất kì số nguyên tố p và bất kì số nguyên c tồn tại k ≤ k() các số nguyên phân biệt xi với 1 ≤ xi ≤ p, và thỏa mãn
k
X
i=1
1
xi ≡c( mod p)
(Ở đây phép nghịch đảo là lấy theo modul p). Điều này được tổng quát hóa bởi Croot trong trường hợp khi tất cả các mẫu số có dạng xki với hầu hết số nguyên dương k.