Really I don't know if there is some error in my idea or simply arduino uno with his 16Mhz can't sample a 4Mhz signal.
You won't be able to achieve these speeds with an interrupt. You will need to use one of the hardware timers with an external clock source. On a UNO, that will be Timer1 with pin 5 as external CS input
Your expected counts in the 23000 range means you can do this on a 16 bit timer without considering overflow count managment. You will need to figure out how to gate the 16 ms period for counting. Report the counts when the period is over. Nick Gammon has a complete example with overflow counts at Gammon Forum : Electronics : Microprocessors : Timers and counters
The FreqCount library also uses the same technique FreqCount Library, for Measuring Frequencies in the 1 kHz to 5 MHz Range
Here is a simplified example I have for a 20ms period which shows how it works. You will need to adapt it for a triggered gate period instead of a fixed period.
//frequency counter using Timer1 counter without overflow count
//TCNT1 16 bit max value = 65,534
//20ms sample period gives frequency counter to a bit over 3.2 mhz
unsigned int dwell = 20000; // dwell in microseconds for counter
unsigned long final_counts;
unsigned long start_time;
unsigned long measured_time;
void setup()
{
Serial.begin(115200);
TCCR1A = 0; //initialize Timer1
TCCR1B = 0;
TCNT1 = 0;
pinMode( 5, INPUT_PULLUP); //external source pin for timer1
}
void loop()
{
start_time = micros();
TCNT1 = 0;//initialize counter
// External clock source on Timer1, pin (D5). Clock on rising edge.
// Setting bits starts timer
TCCR1B = bit (CS10) | bit (CS11) | bit (CS12); //external clock source pin D5 rising edge
while (micros() - start_time < dwell) {} // do nothing but wait and count during dwell time
TCCR1B = 0; //stop counter
final_counts = TCNT1; //frequency limited by unsigned int TCNT1 without rollover counts
measured_time = micros() - start_time;
Serial.print(measured_time); // report resulting counts
Serial.print("\t\t");
Serial.println(50 * final_counts); //20ms sample in Hz
}