최근 Gil Kalai 와 Dick Lipton 은 수 이론과 리만 가설의 전문가 인 Peter Sarnak이 제안한 흥미로운 추측에 관한 멋진 기사를 썼습니다.
어림짐작. 뫼비우스 함수 라고 하자 . 가정하자 F : N → { – 1 , 1 } 이다 C 0 입력과 함수 K 의 이진 표현의 형태로 K 그리고,
Σ K ≤ N μ ( K ) ⋅ F ( K ) = O ( N ) .
참고 경우 것이 우리는의 등가 형태가 프라임 번호 정리 .
업데이트 : MathOverflow의 Ben Green 은 추측을 입증 하는 짧은 논문 을 제공합니다 . 종이를보십시오 .
반면에, 우리는 를 설정함으로써 ( 범위를 약간 수정하여
)의 결과 합은 추정치
가 상부 바운드 μ ( k는 ) 에서 계산 될 수있는 U P ∩ C O U P ⊆ N P ∩ C O N P 에 제안 구속되도록 F ( K ) 추측에은을 완화 할 수없는 N P의 함수 . 내 질문은 :
최저 복잡성 클래스 란 현재 우리가 알고있는 등, 그 함수 F ( K ) 에서 C를 만족 추정
Σ K ≤ N μ ( K ) ⋅ F ( K ) = Ω ( N ) ?
특히, 일부 이론가들은 μ ( k ) 계산 이 P에 없다고 믿었 으므로 다른 P 함수 f ( k )를 제공 할 수 있습니다
요약에서 선형 성장을 의미하는 것은 무엇입니까? 더 나은 범위를 얻을 수 있습니까?